昨天面试在堆排序上载了，只能怪自己之前没有深入理解堆排序的实质和排序过程，今天在这里总结下堆排序，给自己一个交代（基本算法都混了好打脸啊！）。
堆排序是一种选择排序，而这种选择排序是基于顺序存储的完全二叉树的，可设为L[1,...,n]。目的就是利用完全二叉树的双亲节点和孩子节点的内在关系。
堆定义：堆是n个关键字序列，当且仅当该序列满足：
1），L(i)<=L(2*i) && L(i)<=L(2*i+1) 或者 2），L(i)>=L(2*i) && L(i)>=L(2*i+1).
满足1）的叫小顶堆，满足2）的叫大顶堆。
建堆，排序过程（例升序使用大顶堆）：
建堆。
先将关键字序列用顺序存储的完全二叉树表示，从【n/2】到1号节点（根节点）反复调整子树都为堆，初始建堆后有1元素（堆顶）已经排序。
void BuildMaxHeap(ElemType A[], int len) { for (int i=len/2; i>=0; --i)//从n/2 到1反复调整堆 AdjustDown(A, i, len); } void AdjustDown(ElemType A[], int k, int len) { //AdjustDown函数将元素k向下进行调整 A[0] = A[k];//A[0]暂存 for (int i=2*k; i<=len; i *= 2){ if (i<len && A[i]<A[i+1]) ++i;//取较大子节点下标 if (A[0] >= A[i]) break; else { A[k] = A[i]; k = i; } }//for A[k] = A[0]; }
排序。
初始建堆，（需要可输出堆顶元素）然后进行堆顶、底元素交换，重新调整减一后的所有关键字成堆。（排好序的依次从后往前存）
void HeapSort(ElemType A[], int len) { BuildMaxHeap(A, len);//初始建堆 for (i=len; i>1; i--){ //n-1 趟交换和调整堆 swap(A[1], A[i]);//将排好序的A[1]放到堆‘‘底’’（不包括已排好序元素） AdjustDown(A, 1, i-1);//调整堆长度为i-1 }//for }这里说明下可利用堆排序的每次选择一个当前最大（小）性质，在众多元素中选择前k大（小）的元素，而这时要注意升序使用大顶堆前提是对所有元素排序，而仅仅选出前k小元素自然用的是小顶堆。
堆删除 和 插入：
删除堆的元素先将对末、顶元素交换，重新调整堆。
堆插入新节点放末端，再对新节点向上调整。
void AdjustUp(ElemType A[], int k) { //k号节点向上调整 A[0] = A[k]; int i=k/2; while (i>0 && A[i] < A[0]){ A[k] = A[i]; k = i; i = k/2;//继续向上比较 }//while A[k] = A[0]; } 堆排序算法复杂性分析：O(1)和O(nlogn)
空间效率：仅使用常数个辅助单元，空间复杂度O(1)；
时间效率：建堆O(n)（实验证明小于4*n），n-1次下调，每次下调时间O(h)，故堆排时间好坏平均都为O(nlogn)。
-------------------------------------------------------------------------------
#include <iostream> #include <vector> using namespace std; typedef int ElemType; void BuildMaxHeap(ElemType A[], int len); void AdjustDown(ElemType A[], int k, int len); void HeapSort(ElemType A[], int len); void AdjustUp(ElemType A[], int k); int main() { int n; cout << "Please input the size:" << endl; cin >> n; cout << "Please input the numbers need to sort" << endl; vector<int> vec(n+1, 0); for (int i=1; i<=n; ++i) cin >> vec[i]; HeapSort(&vec[0], n); for (int i=1; i<=n; ++i) cout << vec[i] << ' '; return 0; } void BuildMaxHeap(ElemType A[], int len) { for (int i=len/2; i>=0; --i)//从n/2 到1反复调整堆 AdjustDown(A, i, len); } void AdjustDown(ElemType A[], int k, int len) { //AdjustDown函数将元素k向下进行调整 A[0] = A[k];//A[0]暂存 for (int i=2*k; i<=len; i *= 2){ if (i<len && A[i]<A[i+1]) ++i;//取较大子节点下标 if (A[0] >= A[i]) break; else { A[k] = A[i]; k = i; } }//for A[k] = A[0]; } //sort void HeapSort(ElemType A[], int len) { BuildMaxHeap(A, len);//初始建堆 for (int i=len; i>1; i--){ //n-1 趟交换和调整堆 swap(A[1], A[i]);//将排好序的A[1]放到堆‘‘底’’（不包括已排好序元素） AdjustDown(A, 1, i-1);//调整堆长度为i-1 }//for }
