小指针

V1

2022/06/03阅读:19主题:凝夜紫

有趣的数据结构二叉堆的实现

封面原图
封面原图

本文参考:https://www.acwing.com/video/264/

二叉堆

堆是个很大的概念,而本文中的堆,是由二叉树来实现的,所以其实本文的堆特指为二叉堆

概念

优先队列:一种特殊的队列,顾名思义,它可以在O(1)的时间复杂度下pop出max/min。

二叉堆:堆有多种的形式,但是我们一般而言的heap就是二叉堆,即由完全二叉树来实现的堆,比如:python中的heapq。

二叉堆是优先队列的一种实现形式。

堆的作用

一般而言,堆的主要作用有以下几点:

  1. 快速的peek出max/min元素,时间复杂度O(1)。
  2. 快速的pop出max/min元素,时间复杂度O(1)。
  3. 快速的插入一个数到堆中,时间复杂度O(logn)。

堆的结构

二叉堆的结构其实就是一颗满足堆性质的完全二叉树,二叉树的每个节点均有权重,根据权重的不同,我们又可以分成大根堆小根堆

其中大根堆的重要性质是所有节点的权重均小于等于其父节点,也就是说大根堆的root节点一定是最大的

反之,小根堆与大根堆正好相反,小根堆的所有节点的权重均大于等于其父节点,也就是说小根堆的root节点一定是最小的

堆的存储

根据完全二叉树的性质,我们可以使用数组来存储整棵树。具体地:

  1. 把节点编号(是节点编号而非权重)作为数组中存储的下标;
  2. 左子节点编号为父节点编号乘2;
  3. 右子节点编号为父节点编号乘2加1;

使用这种方式,我们把小根堆中的元素标上编号,并且存储到数组中。

这种方式有什么好处呢?显而易见的是,节省空间,与普通的树结构存法(邻接表等)相比,不需要指针来判断父子节点关系,另一个好处是可以直接用 节点编号除以2 来快速的获取父节点

实现堆的两个主要操作

我们可以发现,无论大根堆还是小根堆,为了满足相关的性质都需要调整节点在堆中的位置,而调整节点在堆中的位置的操作,我们分为两种,一种是将节点下沉(down),一种是将节点上升(up),下面以小根堆为例:

  1. 参数说明:

    1. h数组 存储堆中所有的元素,定义在全局;
    2. 节点u 当前正在调整的节点,由方法的参数传入;
    3. idx 当前h数组中元素的最大下标(或者叫 数组中元素个数),定义在全局;
  2. down: 因为是小根堆,必须要保证所有节点的权重均大于等于其父节点,为了满足这一点,我们要比较当前节点和它的两个子节点,选出三个节点中最小的那个当做新的父节点,具体的做法是:

    1. 初始化 当前最小节点t 为 当前节点u ;
    2. 比较 当前最小节点t 和 当前节点u 的左子节点u*2 的权重大小,如果左子节点比u更小,说明u需要下沉,更新 当前最小节点t 为 u的左子结点;
    3. 比较 当前最小节点t 和 当前节点u 得右子节点u*2+1 的权重大小,如果右子节点比t更小,同样说明u需要下沉,更新 当前最小节点t 为 u的右子结点;
    4. 如果当前最小节点t 和 当前节点u 不相同,则说明当前节点u 大于它的儿子节点,不符合小根堆性质,所以把当前节点u 与 当前最小节点t 交换(也就是把 非当前最小节点的u 下沉,所以称为down);
    5. 递归 down(t),以保证当前节点的调整不会影响整体上小根堆性质,最坏情况是从根节点down到叶子节点,也就是down操作的最坏时间复杂度为O(logn),其中n为树的高度。
void down(int u) {
    int t = u;  // 临时存储 最小节点 以便后续比较。
    // u * 2 为左子节点, 如果左子结点小于等于数组中的最大下标,说明左子节点存在;
    // 那么我们判断左子结点的值h[u * 2] 是否小于 当前节点h[t],符合条件则记录t为左子节点。
    if (u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;
    // u * 2 + 1 为右子节点,同理,右子节点也需要和 当前节点h[t] 比较。
    if (u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    // 如果 t 和 u 不相同,说明最小节点有过变更,则交换u和当前的最小节点。
    if (u != t) {
        swap(u, t);
        // 递归 down(t) 
        down(t);
    }
}
  1. up:与down操作正好相反,down是把父节点下沉,而up操作是把一个节点上升,即,交换一个节点和它的父节点,以达到小根堆的性质。
    1. 判断 当前节点u 是否存在 父节点(u/2),如果父节点(u/2)是大于 当前节点u 的说明不符合小根堆性质,则把当前节点u 与父节点交换(即,把更大的当前节点和其父节点互换,以满足小根堆,每个节点都小于等于它的子节点)。
    2. 循环 u /= 2,把当前的节点的父节点置为新的当前节点(当然也可以像down操作一样使用递归)。
void up(int u) {
    // 父节点 u / 2
    while (u / 2 && h[u / 2 ] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;  // u = u / 2 变成父节点
    }
}

实现堆的功能

如果能理解,上面的两种操作,我们就可以用这两种操作来实现一个二叉堆。

  1. peek出max/min,也就是选出最大或者最小元素,那么直接根据大根堆/小根堆的性质,堆顶(根节点)就是max/min。
// 大根堆的根节点即是最大值,小根堆为最小值。
int get_top() {
    return h[1];
}
  1. pop操作,也就是删除堆顶元素。在删除的时候,如果直接删除掉堆顶的元素,那么会出现一种情况:补充新的根节点,需要把两个子节点较小的那个上升;上升后,为了补充缺失子节点,又要判断子节点的两个子节点哪个需要上升,一直循环到叶子节点,这样无疑是很麻烦的。

    所以,我们可以使用一个小技巧来删除,即,使用最后的元素来覆盖根节点,删掉最后的元素,把根节点down一遍即可。总时间复杂度是O(logn)。

void pop() {
    h[1] = h[idx -- ];
    down(1);
}
  1. insert操作,也就是插入一个数到堆中,为了避免影响到堆中现有元素,我们同样使用一个小技巧来插入元素,即,先把元素放到最后,然后对其执行up操作即可。总时间复杂度同样是O(logn)。
void insert(int val) {
    h[++ idx] = val;
    up(idx);
}

进阶功能

上面的三种功能,是堆的标准功能,也就是各个语言提供的标准堆支持的功能,而我们实现的堆,还可以提供进阶的功能:

  1. 删除任意一个元素k。
  2. 修改任意一个元素k。

难点

可以直接使用现有的down和up两种操作来实现进阶功能吗?

注意观察down和up的操作就知道,在这个过程中,我们是不记录元素的顺序的。什么意思呢?注意两个操作中的swap函数,我们交换的是节点的值,而节点的值一但被交换,就可能被连续交换,最后我们不知道它在那个节点上。

为了解决这个问题,我们使用一个 映射数组ph 来记录节点和它对应的值。

如何理解呢?

首先要理解一点,对于第k个插入的元素,初始时候k就是idx,这是因为我们是从末尾开始插入的(具体见insert函数),所以我们认为初始时,h[k]就是我们插入的值,此时它在idx这个位置,也就是ph[idx]=k。思考一下,这样做的好处:我们可以通过 h[ph[idx]] 来访问到这个值

那么,当k移动之后,就把它移动到对应的idx就可以了,这样是不是就可以完成进阶功能了呢?

其实还是不行,注意,进阶功能都是在操作k这个元素,那么k这个元素是什么呢?其实就是h[idx],也就是h中实际存储的值。

我们来结合insert函数来理解,在insert函数中,至关重要的一步是h[++ idx] = val;,这一步表示的含义是**新添加一个元素(++idx)到 堆h ,这个元素的下标是idx,而h[idx]是这个元素的值,初始时也是h[k] **。

我们刚才在交换的时候存储了idx到k的映射,而当我们想找到这个值的时候,也就是h[k]的时候,没有办法通过k找到idx,换句话说就是 可以通过ph[idx]就是k,而这个k它只是个下标,实际的值我们不知道,也就是说通过这个k我们找不到idx(此idx非彼idx,这个idx表示k最初对应的实际值)

解决这个问题也很简单,即再引入一个 映射数组hp 表示k与idx的映射,也就是hp[k]=idx

(PS:笔者的自言自语,这里的两个映射数组,真的较难理解,我自己也画图研究了好久,为了读者朋友们不走弯路,我下面用个直观的示例解释一下。)

假设此时的状态为idx=6,将要加入一个值为10,那么根据我们上面的分析可知新加入的10对应的初始idx=7,k=7,此时我们也应该初始化ph[7]=7,hp[7]=7

OK,假设,执行了一次up操作之后,新加入的10交换到了点idx=3这个点,那么hp[7]应该变成3,表示点k(7)对应的idx变成了3;而ph[hp[7]]也应该与idx=3的交换,表示最初idx=7的这个点下标k现在映射到了idx=3的这个点的k上。(这个例子个人觉得也不是很清晰,请往下看图。)

  1. 只使用ph数组的情况下,我们可以在图中看到,交换节点的同时,ph[idx]指向也交换了,这样我们就能通过idx找到对应的值,既idx=j对应3。但是我们在进阶操作的时候,需要操作第k个点,比如操作k=7这个点,我们现在只能通过idx找到k(或者叫值),而无法知道k=7这个点对应的哪个idx。

  2. 而使用了hp数组之后,我们就记录了k与idx的对应关系,因此当我们需要操作元素k的时候,就可以hp[k]找到idx,然后h[ph[idx]]找到这个k对应的值。连起来就是h[ph[hp[k]]]为k的值。

进阶操作的交换

在进阶操作里,我们要把标准操作中使用的swap函数换成我们自己的swap。

// 其中a、b是两个需要交换的元素的下标
void my_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]); 
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

请注意,其中的前两步交换顺序不能改变,因为第一步中明显依赖了hp数组,所以要先交换ph,再交换hp。

对标准操作的影响

很显然,想要使用进阶操作,那么在标准操作的时候,也需要改变。

其中,down和up操作中的swap需要换成my_swap,并且插入函数需要做出如下改动。

void insert(int val) {
    k ++ ;
    idx ++ ;
    ph[k] = idx;
    hp[idx] = k;
    h[idx] = val;
    up(idx);
}

进阶操作:1.删除第k个元素

操作与删除堆顶元素相同,把最后一个元素idx覆盖k,然后删除最后一个元素(idx -- ),然后进行down或者up。

void del(int k) {
    // 先拿到k对应的idx,防止后面交换时候改变。
    k_idx = ph[k]; 
    // 交换之后,此时ph[k]指向堆中最后一个元素idx,
    // 还好我们上一步保存了源ph[k],也就是k_idx。
    my_swap(k_idx, idx);
    idx -- ;
    // 注意,k_idx可能在树的中间,
    // 而执行down或者up都可以让它归位(符合堆的性质)
    // 所以,这俩函数最多只会执行一个。
    down(k_idx), up(k_idx);
}

进阶操作:2. 修改第k个元素为x

这个就比较简单了,我们在分析中就说了h[ph[k]]就是k的值。

void update(int k, int x) {
    k_idx = ph[k];
    h[k_idx] = x;
    down(k_idx), up(k_idx);
}

大家,可能有点疑惑,在进阶操作中,好像hp数组没有体现出来作用啊?其实不是的,hp数组的最大作用在于维护k的正确性,也就是只有在交换时候使用了hp数组,swap(ph[hp[a]], ph[hp[b]]),才能保证h[ph[k]]是正确的。

标准功能:数组建堆

如果读者堆(heap)用的多的话,就会知道还有一个很常用的标准功能:将数组改建成堆。

在python里,这个api是heapq.heapify(x),其中x是数组,如果看这个api的介绍,你会发现这是一个线性时间内的操作。 线性时间建堆

这就奇怪了,根据我们上面分析的,每个元素的插入是O(logn)的复杂度,那么n个元素插入到堆中不就是O(nlogn)吗?

是的,所以这里并没有把每个元素都插入一遍,采用的建堆方法是循环 n/2 ~ 1 执行down操作

for (int i = n / 2; i > 0; i -- ) {
    down(i);
}

建堆的正确性

思考一下上面的建堆,为什么就能将数组转换成堆呢?

这依赖完全二叉树的一个重要的性质:当完全二叉树有n个节点的时候,其叶子节点个数为n/2

这个性质有啥用嘞?因为,我们知道堆的性质,无论是大根堆还是小根堆,叶子节点都一定满足堆的性质,因为叶子节点没有子节点。也就是说这n/2个叶子节点已经不需要我们主动去操作了,所以我们从最后一个非叶子节点开始操作,而最后一个非叶子节点是什么呢?

我们知道最后一个叶子节点就是n,而n是一定有父节点的,它的父节点就是最后一个非叶子节点,还记得我们计算父节点的方式嘛?就是用 当前节点除以2 ,也就是n/2。(注意上面的n/2表示叶子节点的个数,而这里的n/2表示最后一个非叶子节点的下标。)

因此,我们从 最后一个非叶子节点(n/2)循环到1,每次执行down操作,这样就让堆中的所有元素都满足堆的性质啦~

建堆的时间复杂度

分析时间复杂度同样需要知道一个关于完全二叉树的性质:完全二叉树除了最后一层外,其他所有层均为满节点。所以倒数第二层会有n/4个节点,而倒数第三层会有n/8个节点。

假设最坏情况,需要把 倒数第二层的n/4个节点 全部 down到 倒数第一层,则需要n/4 * 1的时间;同理,把倒数第三层的n/8个节点 全部down到最后一层,则需要n/8 * 2的时间,根据以上规律,我们可以推出如下求时间复杂度的公式:

整理一下该公式,把n提出来:

假设:

那么:

然后用

而公式 一定是小于1的,所以这种建堆的时间复杂度就是O(n)的。

Code

整理一下,完整的二叉堆的简易实现。

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;
int n;
int h[N], idx, ph[N], hp[N];

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

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

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

void insert(int val) {
    k ++ ;
    idx ++ ;
    ph[k] = idx;
    hp[idx] = k;
    h[idx] = val;
    up(idx);
}

void del(int k) {
    k_idx = ph[k]; 
    heap_swap(k_idx, idx);
    idx -- ;
    down(k_idx), up(k_idx);
}

int get_top() {
    return h[1];
}

void heapify(x) {
    for (int i = x.size() / 2; i > 0; i -- ) {
        down(i);
    }
}

总结

一般而言,各个编程语言提供的堆功能相差无几,最核心的功能就是快速的找出最值以及快速的插入一个值。而我们自定义的堆,除了满足基本操作外,还支持“反悔”,可以根据插入的顺序删除或修改中间插入的元素

自定义堆时候,有两个操作是狠关键的,一个是down、一个是up,他们都可以使某个元素符合堆的性质。

在定义进阶操作的时候,理解两个映射数组ph、hp是非常关键的。

理解堆的各种操作的实现,在应用的时候无疑可以起到事半功倍的效果。加油~~

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1