一.堆的概念及结构
1.概念
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2.堆的性质：
A.堆中某个节点的值总是不大于或不小于其父节点的值；
B.堆总是一棵完全二叉树。
其实堆是一种二叉树，通常我们都是用数据表实现，也就是说堆的底层是数组，数组中的小标表示二叉树的节点，所以在实现堆之前，我们有必要了解完全二叉树中节点之间的关系。
1.理解父节点 parent 和子节点 child；
2.了解父节点与子节点之间的关系：
A.parent=（child-1）/2；
B.左孩子child=2*parent+1；
C.右孩子child=2*parent+2。
二.接口实现
A.初始化 Heapinit 销毁 Heapdestroy
这里的初始化和销毁都很简单，相信这对学到堆的人并不是什么难事，和顺序表的操作是一样的，如果实在不理解的话，请看 -> 顺序表
B.插入 Heappush 向上调整 AdjustUp
1.Heappush
插入数据很简单，直接对数组赋值，然后 size 再加加就行了，但是在插入完数据后，我们得保证它是堆，所以这就需要用到向上调整这个函数。
2.AdjustUp
假设我们建的是大堆，我们将新插入的节点与它的父节点比较：
1.如果比它的父节点大，则与其交换，所以交换后的父节点就成为了子节点，再与其父节点比较，以此类推；
2.如果child<=0 则结束循环。
1. void Swap(HPdatatype* p1, HPdatatype* p2) //交换函数 2. { 3. HPdatatype tmp = *p1; 4. *p1 = *p2; 5. *p2 = tmp; 6. } 7. 8. void AdjustUp(HPdatatype* arr, int child) //向上调整 9. { 10. assert(arr); 11. 12. int parent = (child - 1) / 2; 13. 14. while (child > 0) 15. { 16. if (arr[child] > arr[parent]) 17. { 18. Swap(&arr[child], &arr[parent]); 19. child = parent; 20. parent = (child - 1) / 2; 21. } 22. else 23. break; 24. } 25. } 26. 27. void Heappush(Heap* php, HPdatatype x) 28. { 29. assert(php); 30. 31. if (php->size == php->capacity) 32. { 33. HPdatatype* tmp = (HPdatatype*)realloc(php->arr, 2 * sizeof(HPdatatype) * php->capacity); 34. if (tmp == NULL) 35. { 36. perror("realloc fail"); 37. exit(-1); 38. } 39. 40. php->arr = tmp; 41. php->capacity *= 2; 42. } 43. 44. php->arr[php->size] = x; 45. php->size++; 46. 47. AdjustUp(php->arr, php->size - 1); //注意这里要传size-1，因为size表示的是下一个位置 48. }
