1 堆排序拥有插入排序的优点 （是一种原地排序算法只需要存储常数个元素在输入数组以外 即省空间），
同时拥有合并排序算法的复杂度 nlgn，逼格有点高
2 堆数据结构 是一个数组对象，可以被视为一颗完全二叉树，树中的每个结点的值 与 数组中存放的值 对应（看图）
完全二叉树，树中每一层都是满的，除最后一层，即叶子结点只可能存在于（假如深度为n） 最后一层n和n-1 层，且最后一层严格按照最左边的子树开始填）
a 左边为一颗完全二叉树，右边为一个数组
b 圆圈中的数字表示树中每个结点存储的值
c 结点上方的数字 表示对应的数组下标
d 数组上下连线表示父子关系，且父结点总在子结点的左边
f 当前树的高度为3 ，存储值为8的 4号结点的高度为 1 （注：此处高度 从底层最下面开始计算）
3 二叉堆有两种 最大堆 和 最小堆
最大堆特性：某个结点的值 至多跟父节点一样大 即子节点的值 <= 父节点的值
最小堆特性：与上述相反 父节点的值 <= 即子节点的值
4 一颗完全二叉树有n个结点 （n个元素），则有 [(n/2 + 1) .. n] 中的元素都是树中的叶子 （此书练习6.1-7）
5 在一个含n个元素的堆中，至多有 celling( n/2^(h+1) )个高度为h的结点 (^幂运算符, 此书练习6.3-3）
celling(x): 大于或等于x 的最小整数，即向上取整 例如 celling（3/2）= 2
1 //保持最大堆性质 参数inode为内部结点 注意结点从1开始，数组从0开始 2 void MaxHeapify(int array[], int size, int inode) 3 { 4 int largest= inode; //父结点 5 int left = inode*2; //左子结点 6 int right = inode*2+1; //右子结点 7 8 if (left <= size && array[left-1] > array[largest-1]) 9 { 10 largest = left; 11 } 12 if (right <= size && array[right-1] > array[largest-1]) 13 { 14 largest = right; 15 } 16 17 if (largest != inode) //父结点小于 左子结点 或者 右子结点 18 { 19 int temp = array[inode-1]; //子结点值与父结点值交换 20 array[inode-1] = array[largest-1]; 21 array[largest-1] = temp; 22 23 MaxHeapify(array, size, largest); //再次验证被交换的值的子结点是否满足 最大堆性质 24 } 25 } 26 //建立最大堆 使每一个父结点大于子结点 并且根结点为最大值 27 void BuildMaxHeap(int array[],int size) 28 { 29 for(int i=size/2; i>0; --i) //最多有 size/2 个内部结点 30 { 31 MaxHeapify(array, size, i); 32 } 33 } 34 //堆排序 35 void HeapSort(int array[], int size) 36 { 37 BuildMaxHeap(array, size); //建立最大堆 最大值为根结点 38 int temp = 0; 39 int heapSize = size; 40 for (int i=size; i>1; --i) 41 { 42 temp=array[0]; //交换 根结点的值 与 最后面末尾的结点的值 43 array[0]=array[i-1]; //此时违背了最大堆的性质 44 array[i-1] = temp; 45 46 --heapSize; //保持最大堆的性质之前 先去掉已排好序的元素，即减小堆的大小 47 MaxHeapify(array, heapSize, 1); 48 } 49 }; 50 void main() 51 { 52 _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 53 54 int Array[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; 55 56 HeapSort(Array, 10); 57 58 for (int i=0; i<10; ++i) 59 { 60 cout << Array[i] << endl; 61 } 62 63 system("pause"); 64 }