《画解数据结构》九张图画解二叉堆

2021年11月20日 阅读数:7
这篇文章主要向大家介绍《画解数据结构》九张图画解二叉堆,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
本文已收录于专栏
🌳《画解数据结构》🌳

前言

  在以前的文章 二叉搜索树 中,对于 「 增 」「 删 」「 改 」「 查 」 的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n) ~ O ( n ) O(n) O(n)。缘由是最坏状况下,二叉搜索树会退化成 「 线性表 」 。更加确切地说,树的高度决定了它插入、删除和查找的时间复杂度。
  本文,咱们就来聊一下一种高度始终可以接近 O ( l o g 2 n ) O(log_2n) O(log2n)「 树形 」 的数据结构,它可以在 O ( 1 ) O(1) O(1) 的时间内,得到 关键字 最大(或者最小)的元素。而且可以在 O ( l o g 2 n ) O(log_2n) O(log2n) 的时间内执行插入和删除,通常用来作 优先队列 的实现。它就是:

html

「 二叉堆 」


在这里插入图片描述
点击我跳转末尾 获取 粉丝专属 《算法和数据结构》源码,以及获取博主的联系方式。

1、堆的概念

一、概述

  堆是计算机科学中一类特殊的数据结构的统称。实现有不少,例如:大顶堆,小顶堆,斐波那契堆,左偏堆,斜堆 等等。从子结点个数上能够分为二叉堆,N叉堆等等。本文将介绍的是 二叉堆。git

二、定义

  二叉堆本质是一棵彻底二叉树,因此每次元素的插入删除都能保证 O ( l o g 2 n ) O(log_2n) O(log2n)。根据堆的偏序规则,分为 小顶堆 和 大顶堆。小顶堆,顾名思义,根结点的关键字最小;大顶堆则相反。如图所示,表示的是一个大顶堆。
github

三、性质

  以大顶堆为例,它老是知足下列性质:
  1)空树是一个大顶堆;
  2)大顶堆中某个结点的关键字 小于等于 其父结点的关键字;
  3)大顶堆是一棵彻底二叉树。有关彻底二叉树的内容,能够参考:画解彻底二叉树
以下图所示,任意一个从叶子结点到根结点的路径老是一个单调不降的序列。

  小顶堆只要把上文中的 小于等于 替换成 大于等于 便可。web

四、做用

  仍是以大顶堆为例,堆可以在 O ( 1 ) O(1) O(1) 的时间内,得到 关键字 最大的元素。而且可以在 O ( l o g 2 n ) O(log_2n) O(log2n) 的时间内执行插入和删除。通常用来作 优先队列 的实现。面试

2、堆的存储结构

  学习堆的过程当中,咱们可以学到一种新的表示形式。就是:利用 数组 来表示 链式结构。怎么理解这句话呢?
  因为堆自己是一棵彻底二叉树,因此咱们能够把每一个结点,按照层序映射到一个顺序存储的数组中,而后利用每一个结点在数组中的下标,来肯定结点之间的关系。
  如图所示,描述的是堆结点下标和结点之间的关系,结点上的数字表明的是 数组下标。从左往右按照层序进行连续递增。
算法

一、根结点编号

  根结点的编号,看做者的喜爱。能够用 0 或者 1。本文的做者是 C语言 出身,因此更倾向于选择 0 做为根结点的编号(由于用 1 做为根结点编号的话,数组的第 0 个元素就浪费了)。
  咱们能够用一个宏定义来实现它的定义,以下:express

#define root 0

二、孩子结点编号

  那么,根结点的两个左右子树的编号,就分别为 1 和 2 了。以此类推,按照层序进行编号的话,1 的左右子树编号为 3 和 4;2 的左右子树编号为 5 和 6。
  根据数学概括法,对于编号为 i i i 的结点,它的左子树编号为 2 i + 1 2i+1 2i+1,右子树编号为 2 i + 2 2i+2 2i+2。用宏定义实现以下:数组

#define lson(idx) (2*idx+1)
#define rson(idx) (2*idx+2)

  因为这里涉及到乘 2,因此咱们还能够用左移位运算来优化乘法运算,以下:微信

#define lson(idx) (idx << 1|1)
#define rson(idx) ((idx + 1) << 1)

三、父结点编号

  一样,父结点编号也能够经过数学概括法得出,当结点编号为 i i i 时,它的父结点编号为 i − 1 2 \frac {i-1} {2} 2i1,利用C语言实现以下:数据结构

#define parent(idx) ((idx - 1) / 2)

  这里涉及到除 2,能够利用右移运算符进行优化,以下:

#define parent(idx) ((idx - 1) >> 1)

  这里利用补码的性质,根结点的父结点获得的值为 -1;

四、数据域

  堆数据元素的数据域能够定义两个:关键字 和 值,其中关键字通常是整数,方便进行比较肯定大小关系;值则是用于展现用,能够是任意类型,能够用typedef struct进行定义以下:

typedef struct {
   
   
    int key;      // (1)
    void *any;    // (2)
}DataType;
  • ( 1 ) (1) (1) 关键字;
  • ( 2 ) (2) (2) 值,定义成一个空指针,能够用来表示任意类型;

五、堆的数据结构

  因为堆本质上是一棵彻底二叉树,因此将它一一映射到数组后,必定是连续的。咱们能够用一个数组来表明一个堆,在C语言中的数组拥有一个固定长度,能够用一个Heap结构体表示以下:

typedef struct {
   
   
    DataType *data;  // (1)
    int size;        // (2)
    int capacity;    // (3)
}Heap;
  • ( 1 ) (1) (1) 堆元素所在数组的首地址;
  • ( 2 ) (2) (2) 堆元素个数;
  • ( 3 ) (3) (3) 堆的最大元素个数;

3、堆的经常使用接口

一、元素比较

  两个堆元素的比较能够采用一个比较函数compareData来完成,比较过程就是对关键字key进行比较的过程,以大顶堆为例:
  a. 大于返回 -1,表明须要执行交换;
  b. 小于返回 1,表明须要执行交换;
  c. 等于返回 0,表明须要执行交换;

int compareData(const DataType* a, const DataType* b) {
   
   
    if(a->key > b->key) {
   
   
        return -1;
    }else if(a->key < b->key) {
   
   
        return 1;
    }
    return 0;
}

二、交换元素

  交换两个元素的位置,也是堆这种数据结构中很常见的操做,C语言实现也比较简单,以下:

void swap(DataType* a, DataType* b) {
   
   
    DataType tmp = *a;
    *a = *b;
    *b = tmp;
}

  更加详细的内容,能够参考:《算法零基础100讲》(第16讲) 变量交换算法 这篇文章。

三、空断定

  空断定是一个查询接口,即询问堆是不是空的,实现以下:

bool HeapIsEmpty(Heap *heap) {
   
   
    return heap->size == 0;
}

四、满断定

  满断定是一个查询接口,即询问堆是不是满的,实现以下:

bool heapIsFull(Heap *heap) {
   
   
    return heap->size == heap->capacity;
}

五、上浮操做

  对于大顶堆而言,从它叶子结点到根结点的元素关键字必定是单调不降的,若是某个元素出现了比它的父结点大的状况,就须要进行上浮操做。
  上浮操做就是对 当前结点父结点 进行比较,若是它的关键字比父结点大(compareData返回-1的状况),将它和父结点进行交换,继续上浮操做;不然,终止上浮操做。
  如图所示,表明的是一个关键字为 95 的结点,经过不断上浮,到达根结点的过程。上浮完毕之后,它仍是一个大顶堆。

  上浮过程的 C语言 实现以下:

void heapShiftUp(Heap* heap, int curr) {
   
                  // (1)
    int par = parent(curr);                            // (2)
    while(par >= root) {
   
                                  // (3)
        if( compareData( &heap->data[curr], &heap->data[par] ) < 0 ) {
   
   
            swap(&heap->data[curr], &heap->data[par]); // (4) 
            curr = par;
            par = parent(curr);
        }else {
   
   
            break;                                     // (5) 
        }
    }
}
  • ( 1 ) (1) (1) heapShiftUp这个接口是一个内部接口,因此用小写驼峰区分,用于实现对堆中元素进行插入的时候的上浮操做;
  • ( 2 ) (2) (2) curr表示须要进行上浮操做的结点在堆中的编号,par表示curr的父结点编号;
  • ( 3 ) (3) (3) 若是已是根结点,则无须进行上浮操做;
  • ( 4 ) (4) (4) 子结点的关键字 大于 父结点的关键字,则执行交换,而且更新新的 当前结点 和 父结点编号;
  • ( 5 ) (5) (5) 不然,说明已经正确归位,上浮操做结束,跳出循环;

六、下沉操做

  对于大顶堆而言,从它 根结点 到 叶子结点 的元素关键字必定是单调不增的,若是某个元素出现了比它的某个子结点小的状况,就须要进行下沉操做。
  下沉操做就是对 当前结点关键字相对较小的子结点 进行比较,若是它的关键字比子结点小,将它和这个子结点进行交换,继续下沉操做;不然,终止下沉操做。
  如图所示,表明的是一个关键字为 19 的结点,经过不断下沉,到达叶子结点的过程。下沉完毕之后,它仍是一个大顶堆。

  下沉过程的 C语言 实现以下:

void heapShiftDown(Heap* heap, int curr) {
   
               // (1)
    int son = lson(curr);                             // (2)

    while(son < heap->size) {
   
   
        if( rson(curr) < heap->size ) {
   
   
            if( compareData( &heap->data[rson(curr)], &heap->data[son] ) < 0 ) {
   
   
                son = rson(curr);                     // (3) 
            }        
        }
        if( compareData( &heap->data[son], &heap->data[curr] ) < 0 ) {
   
   
            swap(&heap->data[son], &heap->data[curr]); // (4)
            curr = son;
            son = lson(curr);
        }else {
   
   
            break;                                     // (5) 
        }
    }
}
  • ( 1 ) (1) (1) heapShiftDown这个接口是一个内部接口,因此用小写驼峰区分,用于对堆中元素进行删除的时候的下沉调整;
  • ( 2 ) (2) (2) curr表示须要进行下沉操做的结点在堆中的编号,son表示curr的左儿子结点编号;
  • ( 3 ) (3) (3) 始终选择关键字更小的子结点;
  • ( 4 ) (4) (4) 子结点的值小于父结点,则执行交换;
  • ( 5 ) (5) (5) 不然,说明已经正确归位,下沉操做结束,跳出循环;

4、堆的建立

一、算法描述

  经过给定的数据集合,建立堆。能够先建立堆数组的内存空间,而后一个一个执行堆的插入操做。插入操做的具体实现,会在下文继续讲解。

二、动画演示

三、源码详解

Heap* HeapCreate(DataType *data, int dataSize, int maxSize) {
   
       // (1)
    int i;
    Heap *h = (Heap *)malloc( sizeof(Heap) );                    // (2)
    h->data = (DataType *)malloc( sizeof(DataType) * maxSize );  // (3)
    h->size = 0;                                                 // (4)
    h->capacity = maxSize;                                       // (5)

    for(i = 0; i < dataSize; ++i) {
   
   
        HeapPush(h, data[i]);                                    // (6)
    }
    return h;                                                    // (7)
}
  • ( 1 ) (1) (1) 给定一个元素个数为dataSize的数组data,建立一个最大元素个数为maxSize的堆并返回堆的结构体指针;
  • ( 2 ) (2) (2) 利用malloc申请堆的结构体的内存;
  • ( 3 ) (3) (3) 利用malloc申请存储堆数据的数组的内存空间;
  • ( 4 ) (4) (4) 初始化空堆;
  • ( 5 ) (5) (5) 初始化堆最大元素个数为maxSize
  • ( 6 ) (6) (6) 遍历数组执行堆的插入操做,插入的具体实现HeapPush接下来会讲到;
  • ( 7 ) (7) (7) 最后,返回堆的结构体指针;

5、堆元素的插入

一、算法描述

  堆元素的插入过程,就是先将元素插入堆数组的最后一个位置,而后执行上浮操做;

二、动画演示

在这里插入图片描述

三、源码详解

bool HeapPush(Heap* heap, DataType data) {
   
   
    if( heapIsFull(heap) ) {
   
   
        return false;                  // (1)
    }
    heap->data[ heap->size++ ] = data; // (2)
    heapShiftUp(heap, heap->size-1);   // (3)
    return true;
}
  • ( 1 ) (1) (1) 堆已满,不能进行插入;
  • ( 2 ) (2) (2) 插入堆数组的最后一个位置;
  • ( 3 ) (3) (3) 对最后一个位置的 堆元素 执行上浮操做;

5、堆元素的删除

一、算法描述

  堆元素的删除,只能对堆顶元素进行操做,能够将数组的最后一个元素放到堆顶,而后对堆顶元素进行下沉操做。

二、动画演示

在这里插入图片描述

三、源码详解

bool HeapPop(Heap *heap) {
   
   
    if(HeapIsEmpty(heap)) {
   
   
        return false;                               // (1)
    }
    heap->data[root] = heap->data[ --heap->size ];  // (2)
    heapShiftDown(heap, root);                      // (3)
    return true;
}
  • ( 1 ) (1) (1) 堆已空,没法执行删除;
  • ( 2 ) (2) (2) 将堆数组的最后一个元素放入堆顶,至关于删除了堆顶元素;
  • ( 3 ) (3) (3) 对堆顶元素执行下沉操做;

6、获取堆顶元素

一、算法描述

  获取堆顶元素,就是获取了当前全部元素的最值。

二、动画演示

三、源码详解

DataType HeapTop(Heap *heap) {
   
   
    // assert(!HeapIsEmpty(heap));
    return heap->data[root];     // (1)
}
  • ( 1 ) (1) (1) 直接获取数组的第一个元素就是答案了。

7、堆的销毁

一、算法描述

  销毁时注意释放malloc申请的内存;

二、动画演示

  很遗憾,这个无法动图了。

三、源码详解

void HeapFree(Heap *heap) {
   
   
    free(heap->data);
    free(heap);
}

  有关 🌳 堆 🌳 的的内容到这里就彻底结束了,若是还有什么疑问,能够添加做者微信咨询。
  有关🌳《画解数据结构》🌳 的源码均开源,连接以下:《画解数据结构》


  给本身树立一个「 目标 」是很是重要的,有「 目标 」才会有「 方向 」,有「 目标 」才会有「 动力 」,有「 目标 」才会有「 人生的意义 」。有了「 目标 」,再作必定的「 规划 」,而且「 坚持 」作下去,我相信,「 成功的一天终会到来 」
  说了这么多,只是想创建一个「 愿景 」。这个「 愿景 」就是 —— 「 群人皆佬,共赴大厂 」
  光有「 愿景 」是不够的,咱们须要「 付诸实际行动 」,任何一项大工程都不是「 一朝一夕 」可以完成的,「 制定计划 」 是尤其重要的事情。例如,想要学好算法,至少须要掌握一门语言,能够是 C、C++、Python、Java。这里强烈推荐 C语言,由于俗话说得好:

「 学好C语言,走遍天下都不怕 」

  为了 「 督促你们 」更好的学习,因此我创建了一些团队供各位 「 技术交流 」之用,由于团队大了很差带,因此初期就把团队分好组,这样每一个团队都能有很好的照顾,比一会儿吃成胖子要好得多,固然每一个团队我都会挑选一些 「 精英人员 」做为领袖,以便更好的来达成咱们共同的 「 愿景 」
  这主要是提供给各位志想同道合之士交流沟通的一个桥梁,起到 「 媒介 」的做用。让一样和我 「 志同道合 」的人积极投身到这个事业中来,将祖国的 「 算法 」发扬光大,背靠祖国,面向国际,强我国威,壮我河山!
  用 「 算法 」改变世界, 「 让天下没有难学的算法 」
  我不但愿你是以粉丝的身份加入个人团队,我更但愿咱们是 「 合伙人 」,只是没有任何利益上的输送,我也不会在里面作任何产品的推销,因此, 「 广告商勿扰 」
  大多都是正在上大学的学生,我不想赚学生的钱,毕竟能上学已属不易。并且,不少大学生的激情, 「 引燃 」了我本身的 「 青春 」,因此我很喜欢和大学生交流,有时候也会给他们一些面试以及职场上的建议,长此以往,就成了 「 无话不谈 」的好朋友。
  正是这一点,让我激发了认识更多的人的欲望,毕竟, 「 活到老学到老 」「 靠近优秀的人,使本身变得更加优秀 」,始终保持一个学习的态度,多沟通交流,让本身 「 更增强大 」
  各位成员是有明确共同目标的,这样才能共同成长,大体特征以下:
   ( 1 ) (1) (1) 有强烈欲望「 想要学好C语言 」的人
   ( 2 ) (2) (2) 有强烈欲望「 想要学好C++ 」的人
   ( 3 ) (3) (3) 有强烈欲望「 想要学好数据结构 」的人
   ( 4 ) (4) (4) 有强烈欲望「 想学好算法 」的人
   ( 5 ) (5) (5) 有强烈欲望「 想进大厂 」的人
  若是你知足以上任意一点,那么,咱们就是志同道合的人啦!请经过 「 博主的CSDN主页 」 找到联系方式,联系博主。


🔥让天下没有难学的算法🔥

C语言免费动漫教程,和我一块儿打卡!
🌞《光天化日学C语言》🌞

入门级C语言真题汇总
🧡《C语言入门100例》🧡

几张动图学会一种数据结构
🌳《画解数据结构》🌳

组团学习,抱团生长
🌌《算法入门指引》🌌

竞赛选手金典图文教程
💜《夜深人静写算法》💜

粉丝专属福利

语言入门《光天化日学C语言》(示例代码)
语言训练《C语言入门100例》试用版
数据结构《画解数据结构》源码
算法入门《算法入门》指引
算法进阶《夜深人静写算法》算法模板

  

👇🏻 验证码 可经过搜索下方 公众号 获取👇🏻