二叉堆

二叉堆

说明

在阅读该文章的时候,最好手中有一只纸和笔能够画出二叉堆的结构,会更加容易理解。

二叉树的定义

二叉树是每个结点最多有两个子树的树结构。通常子树被称作左子树右子树

二叉堆的定义

当一颗二叉树的根节点都大于等于(小于等于)它的子节点时,它被称为二叉堆。 如果一个二叉堆的根节点大于等于它的所有子节点,称为最大堆。 如果一个二叉堆的根节点小于等于它的所有子节点,称为最小堆。

完全二叉树的定义

二叉堆是一颗完全二叉树即当一颗子树存在右节点的时候这颗子树一定存在左节点。我们会看到这颗二叉树的节点都是从左往右连续排列的。对于完全二叉树更加严谨的定义为:

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层所有的结点都连续集中在最左边。

二叉堆的存储

由于二叉堆是一颗完全二叉树我们可以使用一个数组来存储,数组的每个元素就是二叉堆中的各个节点。这是因为完全二叉树的节点从左至右是连续的,如果不是连续的话使用数组来存储就会浪费一些空间。
当要存储有N个节点的二叉堆时,一般会用长度为N+1的数组来存储这颗二叉堆。数组索引为1元素就是二叉堆的根节点。索引0的位置就空着不用,这是为了方便计算每颗子树的子节点和父节点的索引。

如果树的某个节点索引是k那么:

  • 该节点的父亲节点索引:k/2 (向下取整)

  • 该节点的左子节点索引:2k+1

  • 该节点的右子节点索引: 2k+2

左子节点索引

unsigned getLeftChildIndex(unsigned index) {
    return index * 2 + 1;
}

右子节点索引

unsigned getRightChildIndex(unsigned index) {
    return this->getLeftChildIndex(index) + 1;
}

父节点索引

unsigned getParentIndex(unsigned index) {
    return index / 2; // C++除法如果两边都是整型的话默认向下取整
}

二叉堆的操作

下面的操作都是以最大堆为二叉堆,即二叉堆的根节点大于等于它的所有子节点。最小堆的操作跟最大堆是一样的,只是节点间的比较不同而已。

shiftUp(上移操作)

如果一个最大堆因为一些操作使得某个节点比它的父节点还要大,此时这颗二叉树就不再满足最大堆的性质。要做的操作是把该节点与它的父节点交换位置来保证以交换位置后的该节点为根节点的这颗子树满足最大堆的性质。这个时候可能会想到如果新的根节点的另外一个子节点比这个新的根节点还要大怎么办?为什么不跟另外一个子节点也进行一次比较操作呢? 答案是因为原来的堆是满足最大堆的性质的,所以另外一个子节点一定小于等于原来的父节点,也就一定会小于新的父亲节点,所以不用进行比较。交换后新的父节点还是有可能比这个新的父节点的父节点还要大,那么就再重复一次之前的操作,这样一层一层向上移动直到堆顶或者遇到的节点不再比它的父节点大为止。整个过程就是shiftUp操作。

具体代码

void shiftUp(unsigned index) {
    // 
    while ((index > 1) && this->container[index] >= this->container[getParentIndex(index)]) {
        swap(this->container[index], this->container[getParentIndex(index)]);
        index = index / 2;
    }
}

while中的index > 1表示该索引不是堆顶索引,this->container[index] >= this->container[index / 2]表示该节点大于它的父亲节点。只要满足这2个条件就交换位置,同时把索引设成原来节点的父节点,一样一层一层向上移动,直到不满足这2条件中的任意一个就退出。

shiftDown(下移操作)

如果一个最大堆因为一些操作使得某个节点比它的子节点还要小,此时这颗二叉树就不再满足最大堆的性质。要做的操作是把这个节点与它子节点中最大的那个节点交换位置。交换后的这个节点的位置可能还是比它的子节点小,那么就重复执行之前的操作一层一层向下移动。直到到达堆底或是遇到的节点不再比它的子节点小。该过程就是shiftDown操作。

具体代码

void shiftDown(unsigned index = 1) {
    // 判断左子节点的索引是否超过了数组的大小,如果超过了,就代表该节点没有左子节点.
    while(this->getSize() >= getLeftChildIndex(index)) { // 如果该节点存在左子节点
        unsigned maxChildIndex = getLeftChildIndex(index); // 暂时把最大的节点设为左子节点
        if (this->getSize() >= getRightChildIndex(index)) { // 如果该节点存在右子节点
            if (this->container[getRightChildIndex(index)] > this->container[getLeftChildIndex(index)]) { // 如果右子节点比左子节点大就把最大的子节点设为右子节点.
                maxChildIndex = getRightChildIndex(index);
            }
        }
        if ((this->container[index] >= this->container[maxChildIndex])) { // 如果当前节点大于等于它最大的子节点,那么就没有打破最大堆的性质,所以直接break掉就好了.
            break;
        }
        // 如果当前节点存在一个子节点比它还要大,那么就交换这2个节点的位置,同时把当前循环的索引设为新的根节点的索引然后继续向下检查.
        swap(this->container[index], this->container[maxChildIndex]);
        index = maxChildIndex;
    }
}

该具体具体的代码实现思路就是先判断该节点是否存在左子节点,如果存在就暂时把最大的节点设为左子节点。然后判断该节点存在右子节点。如果存在的话就判断一下这2个子节点哪一个大,把大的那个设为该节点的最大子节点,再来判断一下当前节点是否大于等于这个找出来的大的子节点,如果成立就退出,因为并没有违背最大堆的性质。不成立的话就说明当前节点存在一个子节点比它还要大,那么就交换这2个节点的位置,同时把当前循环的索引设为新的根节点的索引然后继续向下检查。

取出最大值

由于最大堆的堆顶存放的是这个堆的最大值,所以从堆中取出最大值就是取出堆顶的元素。取出堆顶元素后会打破最大堆的定义,所以我们一般的操作是把堆底的元素移动到堆顶。然后再对堆顶的位置做shiftDown操作就可以恢复最大堆的定义。

具体代码

int extractMax() {
    int root = this->container[1]; // 数组索引1的位置存放的是堆顶的元素
    int tail = this->container[this->getSize()]; // 取出堆底的元素
    // 把堆底的元素放到堆顶然后再对堆顶元素做shiftDown操作
    this->container[1] = tail;
    this->shiftDown(1);
    // 维护堆的大小
    this->size --;
    return root;
}

插入节点

往堆中插入节点的时候直接把新的节点放在堆底后一个节点的位置,然后对新的堆底的位置做shifUp操作。

具体代码

void insert(int element) {
    // 把新的元素放在堆底后一个节点的位置
    this->container[this->getSize() + 1] = element;
    // 对新的堆底的位置做shifUp操作
    this->shiftUp(this->getSize() + 1);
    // 维护堆的大小
    this->size ++;
}

heapify

这个操作可以把一个数组构建成一个最大堆。 就是把任意一个数组通过heapify的操作,可以让其满足二叉堆的性质。

我们为了让整个二叉树都满足最大堆的性质,我们首先要保证这颗二叉树的任意一颗子树满足最大堆的性质也就是父节点大于等于它的子节点。这也体现了分而治之的思想。 所以我们要把一个数组构建成一个最大堆就需要先保证每个节点都要大于等于它的子节点。我们可以选择从数组的最后一个元素开始依次往回做shiftDown操作,这样就保证了不会有某个节点小于等于它的子节点。但是我们发现如果某个节点是一个叶子节点的话那么它根本不需要做任何操作,因为它没有子节点。所以后来优化之后我们可以从最后一个拥有子节点的节点开始往回shiftDown。最后一个拥有子节点的节点也被称为非叶子节点或是最后一个父节点它的索引就是堆底的父节点。

具体实现

heapify(int *arr, unsigned size) {
    // size 就是堆底的位置,它的父节点就是最后一个拥有子节点的节点
    for (int i = this->getParentIndex(size); i >= 1; i --) {
        this->shiftDown(i);
    }
}

兼容最小堆和最大堆

有时候我们需要使用最小堆,但有时候我们又需要使用最大堆,但是它们两个往往代码几乎一模一样只是比较符号的不同,为了复用代码,我们只需要给二叉堆设定一个比较方法即可,比如在初始化最大堆的时候给它传入一个方法,这个方法就用来做比较操作。 当二叉堆中需要做比较的时候调用该方法即可。

如果是一个最小堆,我们的比较方法如下:

bool compare(int a, int b) {
    return a < b;
}

堆中相应地方调用的时候:

if (this->compare(this->container[getRightChildIndex(index)], this->container[getLeftChildIndex(index)])) {
// ........
}

结束语

该文章对堆的性质和常用操作做了阐述,文中的代码使用了C++,数据结构与算法的重点在于思想和逻辑所以大家完全可以在了解了算法思想之后用自己熟悉的任意一门语言来实现。后面还会出一篇关于二叉堆应用和复杂度分析的文章。

完整的代码:https://github.com/acodercat/cpp-algorithms/blob/master/include/binary_heap.h

代码测试:https://github.com/acodercat/cpp-algorithms/blob/master/src/demo/binary_heap.cpp

仓库中的二叉堆是从索引0开始的,所以在父节点索引计算上会有不同。

该仓库还有其他算法与数据结构的相应实现

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,723评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,003评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,512评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,825评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,874评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,841评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,812评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,582评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,033评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,158评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,789评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2 352