最小堆。最大堆

最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

最小堆和最大堆的增删改相似，其实就是把算法中的大于改为小于，把小于改为大于。

生成最大堆：最大堆通常都是一棵完全二叉树，因此我们使用数组的形式来存储最大堆的值，从1号单元开始存储，因此父结点跟子结点的关系就是两倍的关系。

即：heap[father * 2] = heap[leftChild];  heap[father * 2 + 1] = heap[rightChild];

最大堆的初始化

在生成最大堆时，我们可以采取一次次遍历整棵树找到最大的结点放到相应的位置中。

但是这种方法有个不好的地方，就是每个结点都要重复比较多次。

所以我们可以换一种思考的顺序，从下往上进行比较。先找到最后一个有子结点的结点，先让他的两个子结点进行比较，找到大的值再和父结点的值进行比较。如果父结点的

值小，则子结点和父结点进行交换，交换之后再往下比较。然后一步步递归上去，知道所在结点的位置是0号位置跳出。这样就可以有效地减少比较所用到的时间。

但是每一次交换都要重复三步：heap[i] = temp; heap[i] = heap[j]; heap[j] = temp;

当树的结构比较大的时候，就会浪费很多时间。

所以我们可以先把父结点的值存到temp中跟子结点比较，如果子结点大的话就把子结点的值赋值给父结点，再往下比较，最后才把temp的值存到相应的位置。

1. void Initialize(T a[], int size, int ArraySize)
2. {
3. delete []heap;
4. isExist = false;
5. heap = a;
6. CurrentSize = size;
7. MaxSize = ArraySize;
8. //产生一个最大堆
9. for(int i = CurrentSize / 2; i >= 1; i –)
10. {
11. T y = heap[i]; //子树的根
12. //寻找放置y的位置
13. int c = 2 * i; //c的父节点是y的目标位置
14. while(c <= CurrentSize)
15. {
16. //heap[c］应是较大的同胞节点
17. if(c < CurrentSize && heap[c] < heap[c + 1])
18. c ++;
19. //能把y放入heap[c / 2]吗？
20. if(y >= heap[c])
21. break; //能
22. else //不能
23. {
24. heap[c / 2] = heap[c]; //将孩子上移
25. c *= 2;
26. } //下移一层
27. }
28. heap[c / 2] = y;
29. }
30. }

最大堆的插入

最大堆的插入的思想就是先在最后的结点添加一个元素，然后沿着树上升。跟最大堆的初始化大致相同。

1. MaxHeap<T> &Insert(const T&x)
2. {
3. if(CurrentSize == MaxSize)
4. exit(1); //没有足够空间
6. //为x寻找应插入位置
7. //i从新的叶节点开始，并沿着树上升
8. int i = ++ CurrentSize;
9. while(i != 1 && x > heap[i/2])
10. {
11. //不把x放进heap[i]
12. heap[i] = heap[i/2]; //元素下移
13. i /= 2; //移向父节点
14. }
15. heap[i] = x; //这时候才把x放进去
16. return *this;
17. }

最大堆的删除最大堆的删除，即删除最大的元素。我们先取最后的元素提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置

1. MaxHeap<T> &DeleteMax(T &x)
2. {
3. //检查堆是否为空
4. if(CurrentSize == 0)
5. exit(1); //队列空
7. x = heap[1]; //最大元素
8. T y = heap[CurrentSize–]; //最后一个元素
9. //从根开始，重构大堆
10. int i = 1, ci = 2; //ci为i的儿子
11. while(ci < CurrentSize)
12. {
13. if(ci < CurrentSize && heap[ci] < heap[ci + 1]) //比较两个子节点大小，取其大
14. ci ++;
15. //能否放y
16. if(heap[ci] > y) //不能
17. {
18. heap[i] = heap[ci]; //孩子上移
19. i = ci; //下移一层
20. ci *= 2;
21. }
22. else //能
23. break;
24. }
25. heap[i] = y;
26. return *this;
27. }