堆：是具有下列特性的完全二叉树；每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆
堆排序：（两个问题）
1、如何由一个无序序列构建成一个堆
2、如何在输出堆顶元素后，调整剩余元素成为一个新的堆
将待排序的序列构建成一个大顶堆，其实就是从下往上、从右到左，将每个非终点节点当作根节点，将其和其子树调整成大顶堆
将待排序的序列构造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值；如此反复，就能得到一个有序序列啦
class HeapSort {
public static void main(String[] argv){
int[] arr = {50,10,90,40,60,80,70,30,20};
System.out.println("排序前...");
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
System.out.println("排序后...");
heapSort(arr);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
//堆构造
public static void heapBuilder(int[] arr, int s, int length){
int k = s;
int guard = arr[s];//哨兵对象
//此处为什么index = 2*k+1完全二叉树的特性决定，第i个节点其左子节点为2i，右子节点为2i+1
//而数组的索引从0开始，所以此处需要+1
int index = 2*k +1;
while(index<length){
if(index+1 < length){
if(arr[index]<arr[index+1]){
index++;
}
}
if(arr[index] > guard){
arr[k] = arr[index];
k = index;
index = 2*k +1;
} else {
break;
}
}
arr[k] = guard;
}
public static void heapSort(int[] arr){
//堆构造，从第一个非子叶节点开始(arr.length/2-1)
for(int i=arr.length/2-1;i>=0;i--){
heapBuilder(arr,i,arr.length);
}
for(int i = arr.length-1;i>0;i--){
//通过交换，将最大值放入到堆的末尾
int max = arr[0];
arr[0] = arr[i];
arr[i] = max;
heapBuilder(arr,0,i);
}
}
}
运行时间完全消耗在初始构建堆和重建堆时的反复筛选上
在构建堆的过程中，因为是完全二叉树从最下层最右边的非终点节点开始构建，将它与其孩子进行比较和有必要的交换，对于每个非终节点来说，最多两次比较和互换操作，因为整个构建堆的时间复杂度为O(n)
正式排序时，第i此取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的每个节点到根节点的距离为log(2)i+1）,并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O(nlogn)
总体来说，堆排序的时间复杂度为O(nlogn)
网友评论