堆（Heap）

发表于 更新于 分类于 ，
本文字数： 612

通常看为一棵完全二叉树的数组对象

定义

分为 大顶堆 与 小顶堆 两种

大顶堆满足 h[i] > h[2 * i] && h[i] > h[2 * i + 1]

小顶堆满足 h[i] > h[2 * i] && h[i] > h[2 * i + 1]

建堆时对从第 n/2 个数到第 1 个数进行 down 操作即可 最差的时间复杂度为 O(nlogn)

代码实现

down操作

1
2
3
4
5
6
7
8
9
10
11
12
void down(int x)
{
    int t = x;
    if (2 * x <= sz && h[t] > h[2 * x])
        t = 2 * x;
    if (2 * x + 1 <= sz && h[t] > h[2 * x + 1])
        t = 2 * x + 1;
    swap(h[t], h[x]);
    if (x != t)
        down(t);
    return;
}

up操作

1
2
3
4
5
6
7
8
9
10
11
12
void up(int x)
{
    int t = x;
    if (x / 2 >= 1 && h[t] < h[x / 2])
        t = x / 2;
    if (t != x)
    {
        swap(h[t], h[x]);
        up(t);
    }
    return;
}

删除某个元素

1
2
3
4
swap(h[x], h[sz]);
sz--;
down(x);
up(x);
  1. 删除堆顶后只需要 down 一次
  2. 如果想要实现删除或者更改第 k 个插入的元素则需要创建额外的两个数组建立映射，同时在 down 与 up 操作中进行映射的维护