贡献者: 有机物

   堆是一棵完全二叉树,且每个结点上的编号都不小于或不大于其父结点的编号,堆的结点上并没有权值。而二叉堆的结点上具有权值,且满足堆的性质。满足父结点不小于左右两个子结点的二叉堆被称为大根堆,反之为小根堆。大根堆与小根堆都被属于二叉堆。但是一般没有特别指出的堆一般都指二叉堆。

   以一个例题来讲解堆。

   维护一个集合,初始时集合为空,支持如下几种操作:

  1. 插入一个数 $x$;
  2. 输出当前集合中的最小值;
  3. 删除当前集合中的最小值;
  4. 删除第 $k$ 个插入的数;
  5. 修改第 $k$ 个插入的数,将其变为 $x$。

   本题要我们实现一个小根堆,根结点是整课树中最小的结点,父结点永远小于等于左右两个子结点。 C++ STL 中的堆只能实现前 $3$ 个操作。

priority_queue<int, vector<int>, greater<int>> heap;   // 定义小根堆的方式
int t;
cin >> t;
while (t -- )
{
    int x;            
    cin >> x;
    heap.push(x);   // 向队尾插入一个数 x
    cout << heap.top() << endl;     // 输出最小值,即队头
    heap.pop();     // 删除最小值,即删除队头
}

   要想实现随机删除和修改,只能用数组来模拟堆,所以我们讲解一下如何使用数组模拟堆。

   首先需要一个数组 h[N] 用于存储堆中的元素,由于需要在任意位置进行删除和修改,所以需要多开两个数组 ph[N]hp[N]

   ph[i] 的意思是第 $i$ 个插入的数在堆中的下标是什么,而 hp[i] 的意思是在堆中下标是 $i$ 的点是第几个插入的。 比如 ph[1] = ahp[a] = 1

   因为是随机插入和删除,所以在堆中删除或者插入某个值的话必定要进行调整。分为 up 操作和 $down$ 操作,up 是如果一个数不符合堆的性质就要往上调整,$down$ 也同理,因为某个数不符合堆的性质,就要往下调整。

   堆的存储只用开一个一维数组 h[N] 就可以了,父结点是 $i$,左子结点就是 $2 \times i$,右子结点就是 $2 \times i + 1$。 $2 \times i$ 可以写成 u << 1,$2 \times i + 1$ 可以写成 u << 1 | 1。比如父结点的下标是 $1$,左子结点的下标就是 $2$,右子结点的下标就是 $3$。有一点需要注意:下标必须从 $1$ 开始,如果从 $0$ 开始的话左子结点和右子结点的下标均为 $0$,这样显然是不行的。

   插入一个数,就直接在堆的结尾插入一个数就可以了,然后再 up 一遍。

   输出最小值直接输出堆顶,一定是最小值。

   删除最小值直接删除堆顶不太好删,我们可以把堆的结尾的数与堆顶的数交换,再删除堆的结尾的数(交换完之后堆的结尾的数就是堆顶,即最小值)删除,然后再从根节点 down 一遍,这样就实现了删除最小值。

   删除任意一个数与删除最小值类似,都是把堆的结尾的数与要删除的数交换,然后再删除堆的结尾的数,最后要注意进行 up 或 down 操作,为了不判断,干脆两个操作都写上,虽然两个函数都执行了,但其中只有一个函数对堆有影响。

   修改任意一个数直接修改就好了,最后也要注意进行 up 或 down 操作。

   up 操作与 down 操作的时间复杂度都为 $\mathcal{O}(\log_2 n)$,输出最小值是 $\mathcal{O}(1)$ 的。所以除了输出最小值,其他操作的时间复杂度都为 $\mathcal{O}(\log_2 n)$。

   因为有任意删除和修改操作,涉及到第 $k$ 个插入的数,所以不能直接知道第 $k$ 个插入的数在堆中的下标是多少,所以需要写一个独特的 $\mathtt{swap}$ 操作,就有了前面所提到的两个数组 ph[N]hp[N]

   具体看一下代码:

void heap_swap(int a, int b)
{
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    swap(h[a], h[b]);
}

   这三行的代码的意思是:先交换一下 hp 数组,再交换一下对应的 ph 数组,最后再交换堆中的元素。

   举个例子: 第一个插入的数是 $a$,第二个插入的数是 $b$,所以:

   hp[a] = 1hp[b] = 2ph[hp[a]] = ph[1] = aph[hp[b]] = ph[2] = bh[1] = 3h[2] = 4

   先交换一下 hp 数组就有:hp[a] = 2hp[b] = 1

   再交换一下对应的:ph 数组就有:ph[hp[a]] = ph[2] = aph[hp[b]] = ph[1] = b

   最后再交换一下对应的 h 数组:h[1] = 4h[2] = 3

   具体的可以看一下图片:

图
图 1:交换前
图
图 2:交换后

   看一下 down 操作:

void down(int u)
{
    int t = u;    // t 为:父结点、左子结点、右子结点三者的最小值
    if ((u << 1) <= cnt && h[u << 1] < h[t]) t = u << 1;
    if ((u << 1 | 1) <= cnt && h[u << 1 | 1] < h[t]) t = u << 1 | 1;
    if (u != t)    // 需要交换
    {
        heap_swap(u, t);
        down(t);
    }
}

   up 操作:

// up 操作,只和我的父结点进行比较
void up(int u)
{
    int t = u;
    if (u / 2 && h[u / 2] > h[t]) t = u / 2;
    if (u != t)
    {
        heap_swap(u, t);
        up(t);
    }
}

   以上就是堆的基本操作了。


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利