• 售前

  • 售后

热门帖子
入门百科

C语言逐日一练 —— 第19天:二叉堆

[复制链接]
痴痴情先生先s 显示全部楼层 发表于 2022-1-16 21:34:49 |阅读模式 打印 上一主题 下一主题
前言

     在之前的文章 二叉搜刮树 中,对于 「 增 」「 删 」「 改 」「 查 」 的时间复杂度为                                    O                         (                         l                         o                                   g                            2                                  n                         )                              O(log_2n)                  O(log2​n) ~                                    O                         (                         n                         )                              O(n)                  O(n)。缘故起因是最坏环境下,二叉搜刮树会退化成 「 线性表 」 。更加确切地说,树的高度决定了它插入、删除和查找的时间复杂度。
  本文,我们就来聊一下一种高度始终可以或许靠近                                    O                         (                         l                         o                                   g                            2                                  n                         )                              O(log_2n)                  O(log2​n) 的 「 树形 」 的数据结构,它可以或许在                                    O                         (                         1                         )                              O(1)                  O(1) 的时间内,得到 关键字 最大(大概最小)的元素。而且可以或许在                                    O                         (                         l                         o                                   g                            2                                  n                         )                              O(log_2n)                  O(log2​n) 的时间内实行插入和删除,一样寻常用来做 优先队列 的实现。它就是:


   「 二叉堆 」  
   
   
  
文章目次



一、堆的概念

1、概述

  堆是盘算机科学中一类特别的数据结构的统称。实现有很多,比方:大顶堆,小顶堆,斐波那契堆,左偏堆,斜堆 等等。从子结点个数上可以分为二叉堆,N叉堆等等。本文将先容的是 二叉堆。
2、界说

  二叉堆本质是一棵完全二叉树,以是每次元素的插入删除都能包管                               O                      (                      l                      o                               g                         2                              n                      )                          O(log_2n)               O(log2​n)。根据堆的偏序规则,分为 小顶堆 和 大顶堆。小顶堆,顾名思义,根结点的关键字最小;大顶堆则相反。如图所示,表现的是一个大顶堆。

3、性子

  以大顶堆为例,它总是满意下列性子:
  1)空树是一个大顶堆;
  2)大顶堆中某个结点的关键字 小于即是 其父结点的关键字;
  3)大顶堆是一棵完全二叉树。有关完全二叉树的内容,可以参考:画解完全二叉树
如下图所示,恣意一个从叶子结点到根结点的路径总是一个单调不降的序列。

  小顶堆只要把上文中的 小于即是 更换成 大于即是 即可。
4、作用

  照旧以大顶堆为例,堆可以或许在                               O                      (                      1                      )                          O(1)               O(1) 的时间内,得到 关键字 最大的元素。而且可以或许在                               O                      (                      l                      o                               g                         2                              n                      )                          O(log_2n)               O(log2​n) 的时间内实行插入和删除。一样寻常用来做 优先队列 的实现。
二、堆的存储结构

  学习堆的过程中,我们可以或许学到一种新的表现情势。就是:利用 数组 来表现 链式结构。怎么明确这句话呢?
  由于堆本身是一棵完全二叉树,以是我们可以把每个结点,按照层序映射到一个次序存储的数组中,然后利用每个结点在数组中的下标,来确定结点之间的关系。
  如图所示,形貌的是堆结点下标和结点之间的关系,结点上的数字代表的是 数组下标。从左往右按照层序举行连续递增。

1、根结点编号

  根结点的编号,看作者的喜欢。可以用 0 大概 1。本文的作者是 C语言 出身,以是更倾向于选择 0 作为根结点的编号(由于用 1 作为根结点编号的话,数组的第 0 个元素就浪费了)。
  我们可以用一个宏界说来实现它的界说,如下:
  1. #define root 0
复制代码
2、孩子结点编号

  那么,根结点的两个左右子树的编号,就分别为 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。用宏界说实现如下:
  1. #define lson(idx) (2*idx+1)
  2. #define rson(idx) (2*idx+2)
复制代码
  由于这里涉及到乘 2,以是我们还可以用左移位运算来优化乘法运算,如下:
  1. #define lson(idx) (idx << 1|1)
  2. #define rson(idx) ((idx + 1) << 1)
复制代码
  这里利用补码的性子,根结点的父结点得到的值为 -1;
4、数据域

  堆数据元素的数据域可以界说两个:关键字 和 值,此中关键字一样寻常是整数,方便举行比力确定巨细关系;值则是用于展示用,可以是恣意范例,可以用typedef struct举行界说如下:
  1. #define parent(idx) ((idx - 1) / 2)
复制代码


  •                                    (                         1                         )                              (1)                  (1) 关键字;
  •                                    (                         2                         )                              (2)                  (2) 值,界说成一个空指针,可以用来表现恣意范例;
5、堆的数据结构

  由于堆本质上是一棵完全二叉树,以是将它逐一映射到数组后,肯定是连续的。我们可以用一个数组来代表一个堆,在C语言中的数组拥有一个固定长度,可以用一个Heap结构体表现如下:
  1. #define parent(idx) ((idx - 1) >> 1)
复制代码


  •                                    (                         1                         )                              (1)                  (1) 堆元素地点数组的首地点;
  •                                    (                         2                         )                              (2)                  (2) 堆元素个数;
  •                                    (                         3                         )                              (3)                  (3) 堆的最大元素个数;
三、堆的常用接口

1、元素比力

  两个堆元素的比力可以接纳一个比力函数compareData来完成,比力过程就是对关键字key举行比力的过程,以大顶堆为例:
  a. 大于返回 -1,代表须要实行交换;
  b. 小于返回 1,代表须要实行交换;
  c. 即是返回 0,代表须要实行交换;
  1. typedef struct {
  2.     int key;      // (1)
  3.     void *any;    // (2)
  4. }DataType;
复制代码
2、交换元素

  交换两个元素的位置,也是堆这种数据结构中很常见的利用,C语言实现也比力简单,如下:
  1. typedef struct {
  2.     DataType *data;  // (1)
  3.     int size;        // (2)
  4.     int capacity;    // (3)
  5. }Heap;
复制代码
  更加具体的内容,可以参考:《算法零底子100讲》(第16讲) 变量交换算法 这篇文章。
3、空判断

  空判断是一个查询接口,即扣问堆是否是空的,实现如下:
  1. int compareData(const DataType* a, const DataType* b) {
  2.     if(a->key > b->key) {
  3.         return -1;
  4.     }else if(a->key < b->key) {
  5.         return 1;
  6.     }
  7.     return 0;
  8. }
复制代码
4、满判断

  满判断是一个查询接口,即扣问堆是否是满的,实现如下:
  1. void swap(DataType* a, DataType* b) {
  2.     DataType tmp = *a;
  3.     *a = *b;
  4.     *b = tmp;
  5. }
复制代码
5、上浮利用

  对于大顶堆而言,从它叶子结点到根结点的元素关键字肯定是单调不降的,如果某个元素出现了比它的父结点大的环境,就须要举行上浮利用。
  上浮利用就是对 当前结点父结点 举行比力,如果它的关键字比父结点大(compareData返回-1的环境),将它和父结点举行交换,继续上浮利用;否则,制止上浮利用。
  如图所示,代表的是一个关键字为 95 的结点,通过不绝上浮,到达根结点的过程。上浮完毕以后,它照旧一个大顶堆。

  上浮过程的 C语言 实现如下:
  1. bool HeapIsEmpty(Heap *heap) {
  2.     return heap->size == 0;
  3. }
复制代码


  •                                    (                         1                         )                              (1)                  (1) heapShiftUp这个接口是一个内部接口,以是用小写驼峰区分,用于实现对堆中元素举行插入的时间的上浮利用;
  •                                    (                         2                         )                              (2)                  (2) curr表现须要举行上浮利用的结点在堆中的编号,par表现curr的父结点编号;
  •                                    (                         3                         )                              (3)                  (3) 如果已经是根结点,则无须举行上浮利用;
  •                                    (                         4                         )                              (4)                  (4) 子结点的关键字 大于 父结点的关键字,则实行交换,而且更新新的 当前结点 和 父结点编号;
  •                                    (                         5                         )                              (5)                  (5) 否则,分析已经精确归位,上浮利用竣事,跳出循环;
6、下沉利用

  对于大顶堆而言,从它 根结点 到 叶子结点 的元素关键字肯定是单调不增的,如果某个元素出现了比它的某个子结点小的环境,就须要举行下沉利用。
  下沉利用就是对 当前结点关键字相对较小的子结点 举行比力,如果它的关键字比子结点小,将它和这个子结点举行交换,继续下沉利用;否则,制止下沉利用。
  如图所示,代表的是一个关键字为 19 的结点,通过不绝下沉,到达叶子结点的过程。下沉完毕以后,它照旧一个大顶堆。

  下沉过程的 C语言 实现如下:
  1. bool heapIsFull(Heap *heap) {
  2.     return heap->size == heap->capacity;
  3. }
复制代码


  •                                    (                         1                         )                              (1)                  (1) heapShiftDown这个接口是一个内部接口,以是用小写驼峰区分,用于对堆中元素举行删除的时间的下沉调解;
  •                                    (                         2                         )                              (2)                  (2) curr表现须要举行下沉利用的结点在堆中的编号,son表现curr的左儿子结点编号;
  •                                    (                         3                         )                              (3)                  (3) 始终选择关键字更小的子结点;
  •                                    (                         4                         )                              (4)                  (4) 子结点的值小于父结点,则实行交换;
  •                                    (                         5                         )                              (5)                  (5) 否则,分析已经精确归位,下沉利用竣事,跳出循环;
四、堆的创建

1、算法形貌

  通过给定的数据聚集,创建堆。可以先创建堆数组的内存空间,然后一个一个实行堆的插入利用。插入利用的具体实现,会在下文继续解说。
2、动画演示


3、源码详解

  1. void heapShiftUp(Heap* heap, int curr) {               // (1)
  2.     int par = parent(curr);                            // (2)
  3.     while(par >= root) {                               // (3)
  4.         if( compareData( &heap->data[curr], &heap->data[par] ) < 0 ) {
  5.             swap(&heap->data[curr], &heap->data[par]); // (4)
  6.             curr = par;
  7.             par = parent(curr);
  8.         }else {
  9.             break;                                     // (5)
  10.         }
  11.     }
  12. }
复制代码


  •                                    (                         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) 末了,返回堆的结构体指针;
五、堆元素的插入

1、算法形貌

  堆元素的插入过程,就是先将元素插入堆数组的末了一个位置,然后实行上浮利用;
2、动画演示


3、源码详解

  1. void heapShiftDown(Heap* heap, int curr) {            // (1)
  2.     int son = lson(curr);                             // (2)
  3.     while(son < heap->size) {
  4.         if( rson(curr) < heap->size ) {
  5.             if( compareData( &heap->data[rson(curr)], &heap->data[son] ) < 0 ) {
  6.                 son = rson(curr);                     // (3)
  7.             }        
  8.         }
  9.         if( compareData( &heap->data[son], &heap->data[curr] ) < 0 ) {
  10.             swap(&heap->data[son], &heap->data[curr]); // (4)
  11.             curr = son;
  12.             son = lson(curr);
  13.         }else {
  14.             break;                                     // (5)
  15.         }
  16.     }
  17. }
复制代码


  •                                    (                         1                         )                              (1)                  (1) 堆已满,不能举行插入;
  •                                    (                         2                         )                              (2)                  (2) 插入堆数组的末了一个位置;
  •                                    (                         3                         )                              (3)                  (3) 对末了一个位置的 堆元素 实行上浮利用;
五、堆元素的删除

1、算法形貌

  堆元素的删除,只能对堆顶元素举行利用,可以将数组的末了一个元素放到堆顶,然后对堆顶元素举行下沉利用。
2、动画演示


3、源码详解

  1. Heap* HeapCreate(DataType *data, int dataSize, int maxSize) {    // (1)
  2.     int i;
  3.     Heap *h = (Heap *)malloc( sizeof(Heap) );                    // (2)
  4.     h->data = (DataType *)malloc( sizeof(DataType) * maxSize );  // (3)
  5.     h->size = 0;                                                 // (4)
  6.     h->capacity = maxSize;                                       // (5)
  7.     for(i = 0; i < dataSize; ++i) {
  8.         HeapPush(h, data[i]);                                    // (6)
  9.     }
  10.     return h;                                                    // (7)
  11. }
复制代码


  •                                    (                         1                         )                              (1)                  (1) 堆已空,无法实行删除;
  •                                    (                         2                         )                              (2)                  (2) 将堆数组的末了一个元素放入堆顶,相称于删除了堆顶元素;
  •                                    (                         3                         )                              (3)                  (3) 对堆顶元素实行下沉利用;
  

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作