手写堆

STL中的priority_queue虽然用着舒服,但是不支持修改和删除操作,在某些问题上使用确实不太舒服。本文就是记录一下如何手写一个堆。

堆要满足的操作:(以小根堆为例,大根堆同理)

  • 插入一个数
  • 求集合当中的最小值
  • 删除最小值
  • 删除任意一个元素
  • 修改任意一个元素

堆的结构

是一棵二叉树(完全二叉树)。
– 小根堆:父节点小于等于左右儿子
– 大根堆:父节点大于等于左右儿子

堆的存储

用一个一维数组来存储,下标从1开始

堆的基本操作(以小根堆为例)

  • down(x):往下调整(把一个节点向下移),如果一个节点的值变大了,向下移动每次和左、右儿子中最小的进行交换。

  • up(x):向上调整。每次和父节点进行比较,如果比父节点小,则和父节点进行交换。

利用down和up操作可以拼出上述的5个操作。

用size表示堆的大小,heap表示堆(小根堆为例)
1. 插入一个数

heap[++size] = x; up(size);
  1. 求集合中的最小值
heap[1];
  1. 删除最小值
heap[1] = heap[size]; size--; down(1);
  1. 删除任意一个元素
heap[k] = heap[size];
size--;
down(k);
up(k);
  1. 修改任意一个元素
heap[k] = x;
down(k);
up(k);

讨论

如果我们通过插入操作来构建堆,可以发现若插入n个数,最坏O(n logn)

for(遍历n个点)
    插入第i个点

但若我们从倒数第二层的节点开始,从下到上做down操作,从 i = n / 2 开始,每次i–,时间复杂度为O(n)(挺好证明的)。

for(int i = n/2; i; i--)
    down(i);
int n, m;
int h[N], size;

void down(int u)
{
    int t = u;
    if(u*2 <= size && h[u*2] < h[t])
        t = u*2;
    if(u*2+1 <= size && h[u*2+1] < h[t])
        t = u*2 + 1;
    if(u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 && h[u/2] > h[u]) {
        swap(h[u/2], h[u]);
        u /= 2;
    }
}

发表评论

您的电子邮箱地址不会被公开。