堆排序浅析

来源于我的博客 堆排序

最大堆

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆（大顶堆）。 大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值，且要求是完全二叉树。

ps:这里指的堆均为二叉堆(Binary Heap)，最小堆的定义类似

堆排序的核心就是建立堆与重建堆的过程：

建立堆

以数组[4 5 1 6 2 7 3 8]为例

排序

堆排序就是先建立最大堆，取出最大值后剩下的部分再重建堆，依次取出最大值即可。 而通常对数组排序时可以简化为： 1. 建立最大堆(将数组分为[大根堆＋已排序]两部分) 2. 将最大值与堆最后一个叶结点交换，这个最大值并入后面已排序部分，对前面部分的数组重新堆化 3. 重复2直到堆只剩下一个元素，此时数组已经排序完成(小到大)

时间复杂度

n个结点的完全二叉树中：

完全二叉树的深度为[log2(n)]+1度为0的结点(叶结点)数为(n＋1)/2非叶结点数为n/2深度为H的完全二叉树，第i层最多有2^(H-i)个结点

看上面的建堆过程，树深度为H，对于第i层的结点，以它为根建立大根堆需要交换的次数为该子树的深度(H-i)，第i层最多有2^(H-i)个结点 因此总比较次数为 因此建堆过程复杂度为O(n)

堆排时堆顶值与堆尾部值交换，此时堆化过程其实只是堆顶值下沉的过程，最大情况下需要交换的次数为堆的高度log2(n)+1,需要计算n－1次最大值，因此堆排序复杂度为O(N*logN)

C++实现

void HeapfyDown(int *a,int i,int n){ int j,tmp; tmp=a[i]; j=2*i+1; while (j<n) { if((j+1)<n&&(a[j+1]>a[j])) j++; if(a[j]<=tmp) break; a[i]=a[j]; i=j; j=2*i+1;//调整子节点的子节点 } a[i]=tmp; } void MakeMaxHeap(int *a,int n){ for(int i=(n-1)/2;i>=0;i--){ HeapfyDown(a, i, n); } } void HeapSort(int *a,int n){ MakeMaxHeap(a,n); for(int i=n-1;i>=1;i--){ swap(a[i],a[0]); HeapfyDown(a,0,i); } }