完全二叉树， 最大堆 ， 堆排序

脑袋不够用，所以记录下来

python 版本 构建 最大堆

``````class Utils(object):
@staticmethod
def buildMaxHeap(l=None,heap_size=None):
if heap_size is None:
heap_size = len(l)
for i in range(heap_size//2,0,-1):
Utils.maxHeapify(heap_size,i,l)

@staticmethod
def maxHeapify(heap_size,rootIndex,l=None):
left,right,largest = 2*rootIndex,2*rootIndex+1,rootIndex

if left<=heap_size and l[left-1] > l[rootIndex-1]:
largest = left
if right<=heap_size and l[right-1] > l[largest-1]:
largest = right

if largest!=rootIndex:
l[largest-1],l[rootIndex-1] = l[rootIndex-1],l[largest-1]
if largest <= heap_size//2:
Utils.maxHeapify(heap_size,largest,l)
print(l)

if __name__ == '__main__':
l = [10,9,3,2,4,6,5,7,8]
print(l)
Utils.buildMaxHeap(l)
print(l)``````

改为 堆排序

``````class Utils(object):
@staticmethod
def buildMaxHeap(l=None,heap_size=None):
if heap_size is None:
heap_size = len(l)
for i in range(heap_size//2,0,-1):
Utils.maxHeapify(heap_size,i,l)

@staticmethod
def maxHeapify(heap_size,rootIndex,l=None):
left,right,largest = 2*rootIndex,2*rootIndex+1,rootIndex

if left<=heap_size and l[left-1] > l[rootIndex-1]:
largest = left
if right<=heap_size and l[right-1] > l[largest-1]:
largest = right

if largest!=rootIndex:
l[largest-1],l[rootIndex-1] = l[rootIndex-1],l[largest-1]
if largest <= heap_size//2:
Utils.maxHeapify(heap_size,largest,l)
@staticmethod
def heapSort(l=None):
Utils.buildMaxHeap(l)
for i in range(len(l)-1,0,-1):
l[0],l[i] = l[i],l[0]
Utils.buildMaxHeap(l,i)

if __name__ == '__main__':
l = [10,9,3,2,4,6,5,7,8]
print(l)
#     Utils.buildMaxHeap(l)
Utils.heapSort(l)
print(l)``````

java 版

``````package com.ghc.starter.algorithm;
/*

* */
public class SortUtils {
public static int [] array = {10,9,3,2,4,6,5,7,8};

// 完全二叉树 --》最大堆--》堆排序
public static void main(String [] args){
printArray(array);
buildMaxHeap(array,array.length);
printArray(array);
heapSort(array);
printArray(array);
array = new int[]{10,9,3,2,4,6,5,7,8};
printArray(array);
bubbleSort(array);
printArray(array);
}

// 快速排序
public static void quickSort(int [] array){

}
// 冒泡排序
public static void bubbleSort(int [] array){
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-i-1;j++){
if(array[j]>array[j+1]){
swap(array,j,j+1);
}
}
}
}
// 有格式的打印数组
public static void printArray(int [] array){
System.out.print("[");
for(int i=0;i<array.length;i++){
if(i!=array.length-1)
System.out.print(array[i]+",");
else System.out.println(array[i]+"]");
}
}
// 堆排序 基于 下面 构建 最大堆
public static void heapSort(int [] array){
// 如果 数组只有一个元素或者为空则不用排序
if(array==null || array.length<=1) return;
// 否则开始 堆排序
// 先 构建一个 最大堆
buildMaxHeap(array,array.length);
for(int i=array.length-1;i>0;i--){
// 交换 堆顶与 最后位置的值，下一次 跳过 已经排好序的 位置
swap(array,0,i);
// 递归 重复构建 跳过 排好序的位置后的 最大堆
buildMaxHeap(array,i);
}
}
// 根据传入的 数组 构建一个 最大堆 ，最大堆只能保证堆顶是最大值，那么堆排序就是每次取最值后然后调整堆为最大堆
public static void buildMaxHeap(int [] array,int heapSize){
// 从 总节点数的 1/2 之一处开始 逆序 调整 最大堆
for(int i=heapSize/2;i>0;i--){
maxHeapify(array,heapSize,i);
}
}
public static void maxHeapify(int [] array,int heapSize,int rootIndex){
//左叶子结点
int l = 2*rootIndex;
// 右叶子结点
int r = l+1;
// 调整需要的最大值指向
int largest = rootIndex;
//如果 左叶子结点比父节点要大 ，那么修改 largest 指向为 l
if(l<=heapSize && array[l-1]>array[rootIndex-1]){
largest = l;
}
//如果 右叶子结点比父节点要大 ，那么修改 largest 指向为 r
if(r<=heapSize && array[r-1]>array[largest-1]){
largest = r;
}
// 如果 最大值不是 父节点，那么交换 最大值指向与父节点的位置
if(largest!=rootIndex){
swap(array,largest-1,rootIndex-1);
if(largest<=heapSize/2){
// 如果该父节点有子节点，那么对 子节点也递归做 最大堆调整
maxHeapify(array,heapSize,largest);
}
}

}
// 交换 数组中的值
public static void swap(int [] array,int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
``````
原文作者：拂髯客
原文地址: https://www.cnblogs.com/Frank99/p/10107965.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。