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）
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 }
（转载请注明作者和出处^_* Seven++ ）