堆的概念及结构
如果有一个关键码的集合K = 
，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：
且
（或
且
），i = 0,1,2,······，则称为小堆或大堆。
小根堆：父亲小于等于孩子。
大根堆：父亲大于等于孩子。
堆的性质：
（1）堆中某个结点的值总是不大于或不小于其父结点的值；
（2）堆总是一棵完全二叉树。
大根堆可以用来选择最大的数，小根堆可以用来选择最小的数。但大根堆和小根堆不能用来排序（从上图小根堆的排序结构可以看出）。
对堆中的结点进行编号：
由于堆是完全二叉树，物理存储结构就像数组，在堆中，如果已知父亲的下标是parent，则左右孩子的下标为：
leftchild = parent*2+1
rightchild = parent*2+2
如果已知孩子的下标，则父亲下标为：
parent = (child-1)/2
堆的实现
在进行堆的构造和堆排序之前需要了解向下调整算法：
向下调整算法：
如果一棵二叉树的左子树和右子树恰好都是小（大）堆，但只有根结点不满足小（大）堆的定义，如何把这棵二叉树调成小（大）堆呢？需要使用向下调整算法调成小（大）堆
1.选出左右孩子中的小（大）孩子
2.小（大）孩子跟父亲比：
a.如果小孩子比父亲小（大），则让小（大）孩子跟父亲交换，并把原来孩子的位置当成父亲继续往下调整，直到走到叶子结点。
b.如果小孩子比父亲大（小），则不需要处理，调整完成，整棵树已经是最小（大）堆。
如下面这棵二叉树，蓝色框内左右子树都是小根堆，但是堆顶27和左右孩子15、19并不构成小根堆，使用向下调整算法进行调整：
第1步：选出左右孩子中的小孩子，15和19相比，15小，15比父亲27小，15和27交换
第2步：把原来孩子的位置也就是现在27的位置当成父亲继续往下调整
第3步：选出左右孩子中的小孩子，18和28相比，18小，18比父亲27小，18和27交换
第4步：把原来孩子的位置也就是现在27的位置当成父亲继续往下调整
第5步：选出左右孩子中的小孩子，49和25相比，25小，25比父亲27小，25和27交换
第6步：把原来孩子的位置也就是现在27的位置当成父亲继续往下调整，发现27已经是叶子结点了，调整完毕。
如果左子树或右子树不是小根堆呢？就不能使用向下调整算法了吗？答案是需要先把左右子树构造成小根堆，再使用向下调整算法，最后整棵树调成小根堆。同理，如果左子树或右子树不是大根堆，需要先把左右子树构造成大根堆，再使用向下调整算法，最后整棵树调成大根堆。
构造小根堆：
从倒数第一个非叶子结点开始，从后往前，按编号，依次作为子树向下调整。
如
第1步：倒数第一个非叶子结点的下标为(n-1-1)/2，即(7-1-1)/2=3，从倒数第一个非叶子结点编号为3的结点5开始作为子树向下调整，5只有一个孩子4，4比5小，交换4和5
第2步：得到如下二叉树，对前一个编号2的位置即结点3作为子树向下调整，3的两个孩子1和7，1小，交换3和1
第3步：得到如下二叉树，对前一个编号1的位置即结点8作为子树向下调整，8的两个孩子5和2，2小，交换8和2
第4步： 得到如下二叉树，对前一个编号0的位置即结点6作为子树向下调整，6的两个孩子8和1，1小，交换6和1
第5步： 得到如下二叉树，现在以结点6为根结点的子树已经不符合小根堆的定义了，需要向下向下调整，6的两个孩子3和7，3小，交换6和3
此时，二叉树已经是小根堆了，调整完毕
建堆代码：
1. #define _CRT_SECURE_NO_WARNINGS 1 2. void Swap(int *p1, int *p2) 3. { 4. int tmp = *p1; 5. *p1 = *p2; 6. *p2 = tmp; 7. } 8. 9. //向下调整算法 10. AdjustDown(int* a, int n, int parent) 11. { 12. int child = parent * 2 + 1; 13. while (child <n) 14. { 15. //选出左右孩子中的小孩子 16. if (child + 1 < n && a[child + 1] < a[child]) 17. { 18. child++; 19. } 20. //小孩子比父亲小，交换小孩子和父亲，可能导致不满足堆的定义，需要调整 21. if (a[child] < a[parent]) 22. { 23. Swap(&a[child], &a[parent]); 24. parent = child; 25. child = parent * 2 + 1; 26. } 27. //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做 28. else 29. { 30. break; 31. } 32. } 33. } 34. int main() 35. { 36. int a[] = { 6,8,5,9,3,7,2 }; 37. //int a1[] = { 1,2,3,4,5,6,7 }; 38. int n = sizeof(a) / sizeof(a[0]); 39. int i = 0; 40. for (i = (n - 1 - 1) / 2; i >= 0; i--) 41. { 42. AdjustDown(a, n, i); 43. } 44. return 0; 45. }
