数组模拟堆（一）

文章目录

前言

一、堆

二、堆的存储与操作

如何用一维数组存储一个堆

如何实现维护一个堆

插入一个数

求集合当中的最小值

删除最小值

删除任意一个元素

修改任意一个元素

三、例题，代码

AcWing 838. 堆排序

关于本题

AC代码

AcWing 839. 模拟堆

关于本题

AC代码

四、时间复杂度

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：用数组模拟堆，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、堆

堆在STL中就是优先队列，在图中是一颗完全二叉树，关于STL优先队列的讲解见：STL—priority_queue，本文讲解用数组去写一个堆，堆的要求为父节点一定小于两个子节点，本文用到了swap函数，具体操作可见博客：STL—algorithm（1）

二、堆的存储与操作

如何用一维数组存储一个堆

因为堆是一颗完全二叉树，所以我们有如图所示的存储方式：假设父节点是x，那么左节点就是2x，右节点就是2x + 1.

注意我们的数组不能从0开始，否则整个数的节点编号都会是0

如何实现维护一个堆

down操作：如果父节点不是三个节点中最小的点，那么就往下移动，移动的原则是和两个子节点中最小的那个交换

void down(int x)
{
    int t = x;          //t存储的数就是三哥数中最小的那个
    if (x * 2 <= cnt && h[x * 2] < h[t]) t = x * 2;    //如果比左儿子大，就让t为左儿子编号
    if (x * 2 + 1 <= cnt && h[x * 2 + 1] < h[t]) t = x * 2 + 1; //如果比右儿子大，就让t为右儿子编号
    if (t != x)       //证明和左儿子或者右儿子进行了交换
    {
        swap(h[t], h[x]);
        down(t);
    }
}

up操作：和down操作不同，如果这个点比父节点小的话，交换这两个点就足够了

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])           //u的父节点存在且u比父节点小
    {
        heap(u, u / 2);
        u >>= 1;               //等价于 u = u / 2;
    }
}

插入一个数

我们直接在堆的末尾插入一个新的数，然后执行一下up操作

heap[ ++ size] = x;
up(x);

求集合当中的最小值

因为我们模拟堆是实现的小根堆，所以我们取最小值直接就是：

heap[1];

删除最小值

因为我们是拿一个一维数组去存储一个堆的，所以我们要删除最小值得话（头结点）是十分困难的，但是我们删除尾结点是十分简单的，所以我们有如下操作：

heap[1] = heap[size];
size --;
down(1);

删除任意一个元素

和删除最小值一个道理，直接把尾结点覆盖给这个点，然后size --;，注意这个点可能会变大也可能会变小，所以，不管变大变小我们直接down一遍，up一遍即可

heap[k] = heap[size];
size --;
down(k);
up(k);

修改任意一个元素

这里也是不管更改后是变大还是变小反正结果只会执行一次（要么执行down，要么执行up），所以我们不管变大变小我们直接down一遍，up一遍即可

heap[k] = x;
down(k);
up(k);