数据结构 九 堆

堆的定义

heap,可以看作一棵树，只不过在性质方面和树不一样。

堆的性质

  1. 堆是一颗完全树。
  2. 堆的父结点值总是大于等于（最大堆）或者总是小于等于（最小堆）其孩子结点的值。

二叉堆

以最大堆为例

  • 二叉堆满足堆的定义，二叉堆是一个完全二叉树。
  • 当将一个数组看成一个堆的时候，若从零开始，则 2n+1 2n+2 为 n 的孩子。

二叉堆的算法

调整

堆的调整算法即将堆中一个子树进行调整，令其满足堆的定义。这种调整的方法如下。

  1. 若根的值小于孩子的值，则令其与较大的孩子进行交换
  2. 令交换后的结点作为新根重复1直到没有孩子或者比孩子的值要大。

新建一个堆，将一个无序的数组调整为一个堆，算法如下：

  1. 从最后一个非叶子结点向前遍历直到根节点
  2. 对每一个结点进行上述的调整算法。

若对一个已经成序的堆进行调整只需要调整一个改变的结点即可，因为此时只有要处理的结点无序，其余结点都有序。

插入

  1. 将插入到数据插入的二叉堆的最后面
  2. 将该结点的值和其父结点进行比较，若大于其父结点的值则与父结点交换，递归直到无法上浮。

堆的一个重要应用就是堆排序，即将一个数组看成一个堆，进行排序。

删除

  1. 使用数组最后一个结点覆盖要删除的结点完成删除
  2. 对该结点进行调整。

排序

使用堆排序，即将数组调整为最大堆之后将堆顶与堆尾元素互换，即将最大的元素放在数组尾部。调整堆。重复直到完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//堆排序
void heap_sort(int *begin, int *end)
{
    int num = end - begin;
    //首先建立大根堆，即对 n/2 - 1 为根的子树进行调整。
    for (int i = num / 2; i >= 0; i--)
        heap_adjust(begin, end, i, num);
    //循环输出最大值，并调整堆。
    for (int i = 0; i <= num - 1; i++)
    {
        int temp = begin[0];
        begin[0] = begin[num - i - 1];
        begin[num - i - 1] = temp;
        heap_adjust(begin, end, 0, num - i - 1);
    }
}
//调整heap的一个子树
void heap_adjust(int *begin, int *end, int seq, int len)
{
    //将树根与其最大的孩子进行交换，递归直到叶子。
    int temp = begin[seq];
    for (int i = seq * 2 + 1; i < len; i = i * 2 + 1)
    {
        //指向大的孩子
        if (i + 1 < len && begin[i] < begin[i + 1])
            i++;
        if (temp < begin[i])
        {
            begin[seq] = begin[i];
            seq = i;
        }
        else if (temp >= begin[i])
            break;
    }
    begin[seq] = temp;
}