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

显示全部楼层

前言

在之前的文章 「二叉搜刮树」 中，对于 「增」「删」「改」「查」 的时间复杂度为                                  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) 的时间内实行插入和删除，一样寻常用来做优先队列的实现。它就是：

「二叉堆」


文章目次

一、堆的概念

1、概述

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

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

3、性子

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

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

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

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

1、根结点编号

根结点的编号，看作者的喜欢。可以用 0 大概 1。本文的作者是 C语言出身，以是更倾向于选择 0 作为根结点的编号（由于用 1 作为根结点编号的话，数组的第 0 个元素就浪费了）。
我们可以用一个宏界说来实现它的界说，如下：

#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。用宏界说实现如下：

#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)
复制代码

这里利用补码的性子，根结点的父结点得到的值为 -1；
4、数据域

堆数据元素的数据域可以界说两个：关键字和值，此中关键字一样寻常是整数，方便举行比力确定巨细关系；值则是用于展示用，可以是恣意范例，可以用typedef struct举行界说如下：

#define parent(idx) ((idx - 1) / 2)
复制代码

( 1 ) (1) (1) 关键字；
( 2 ) (2) (2) 值，界说成一个空指针，可以用来表现恣意范例；

5、堆的数据结构

由于堆本质上是一棵完全二叉树，以是将它逐一映射到数组后，肯定是连续的。我们可以用一个数组来代表一个堆，在C语言中的数组拥有一个固定长度，可以用一个Heap结构体表现如下：

#define parent(idx) ((idx - 1) >> 1)
复制代码

( 1 ) (1) (1) 堆元素地点数组的首地点；
( 2 ) (2) (2) 堆元素个数；
( 3 ) (3) (3) 堆的最大元素个数；

三、堆的常用接口

1、元素比力

两个堆元素的比力可以接纳一个比力函数compareData来完成，比力过程就是对关键字key举行比力的过程，以大顶堆为例：
a. 大于返回 -1，代表须要实行交换；
b. 小于返回 1，代表须要实行交换；
c. 即是返回 0，代表须要实行交换；

typedef struct {
    int key;      // (1)
    void *any;    // (2)
}DataType;
复制代码

2、交换元素

交换两个元素的位置，也是堆这种数据结构中很常见的利用，C语言实现也比力简单，如下：

typedef struct {
    DataType *data;  // (1)
    int size;        // (2)
    int capacity;    // (3)
}Heap;
复制代码

更加具体的内容，可以参考：《算法零底子100讲》(第16讲) 变量交换算法这篇文章。
3、空判断

空判断是一个查询接口，即扣问堆是否是空的，实现如下：

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;
}
复制代码

4、满判断

满判断是一个查询接口，即扣问堆是否是满的，实现如下：

void swap(DataType* a, DataType* b) {
    DataType tmp = *a;
    *a = *b;
    *b = tmp;
}
复制代码

5、上浮利用

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

上浮过程的 C语言实现如下：

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

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

6、下沉利用

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

下沉过程的 C语言实现如下：

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

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

四、堆的创建

1、算法形貌

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

3、源码详解

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) 给定一个元素个数为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、源码详解

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) 堆已满，不能举行插入；
( 2 ) (2) (2) 插入堆数组的末了一个位置；
( 3 ) (3) (3) 对末了一个位置的堆元素实行上浮利用；

五、堆元素的删除

1、算法形貌

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

3、源码详解

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) 堆已空，无法实行删除；
( 2 ) (2) (2) 将堆数组的末了一个元素放入堆顶，相称于删除了堆顶元素；
( 3 ) (3) (3) 对堆顶元素实行下沉利用；

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

工作时间

工作时间

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

本帖子中包含更多资源

火星云矿 | 预约S19Pro，享500抵1000！