堆的实现（Heap）（C语言）

堆的实现（Heap）（C语言）

引用

CSDN

1.

https://blog.csdn.net/blkblizzard/article/details/139241900

堆是一种常用的数据结构，它具有独特的性质和操作方式。本文将详细介绍堆的实现原理，包括堆的定义、代码实现以及具体的操作函数。通过阅读本文，你将能够理解堆这种数据结构及其在编程中的应用。

一、堆的介绍

要想了解堆，我们先要了解什么是树形结构。这张图大家都不陌生，程序员的神树，完美的二叉树。

那么堆的本质也是一种二叉树，但是其中蕴含了节点数据大小之间的关系。就如下面这张图，左边是小堆（Min Heap）其特点是每个根节点都比自己的子节点要小。右边是大堆（Max Heap）其特点是每个根节点都比自己的子节点大。

在链式结构和顺序结构中选择，由于堆一定是一个完全二叉树，也就是说用顺序结构来依次记录节点不会出现空节点的情况，并且相较于链式结构，不需要繁琐的关系建立，所以我们将用顺序结构实现堆。

二、代码实现

1.Heap.h

在堆的结构体设计中，首先用数组来记录元素，用size来记录数组元素个数（也就是末位叶节点的位置），用capacity进行动态扩容。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
typedef HPDataType;
typedef struct Heap {
    HPDataType* a;//设置顺序结构数组来记录堆元素
    int size;//记录堆节点位置，完全二叉树位置。
    int capacity;//记录堆数组大小，顺序结构大小
}HP;
void HeapInit(HP* php);//堆初始化
void HeapDestroy(HP* php);//堆销毁
void HeapPush(HP* php, HPDataType x);//堆添加元素
void HeapPop(HP* php);//堆节点删除目的：删除根节点
HPDataType HeapTop(HP* php);//返回堆顶元素
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);  

2.Heap.c

1.堆初始化(HeapInit)

void HeapInit(HP* php) {
    assert(php);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}  

2.堆的销毁(HeapDestroy)

void HeapDestroy(HP* php) {
    assert(php);
    free(php->a);
    php->a=NULL;
    php->size = php->capacity = 0;
}  

3.进堆(HeapPush)

进堆默认是进到最后一个叶节点，在进之前要先判断数组空间是否足够。问题来了，进入的数会打乱原来堆的结构，那么如何将堆重新变成大/小堆和谐的状态呢，这时我们就需要这个末尾的节点向上移动，以小堆为例，若插入节点小于根节点就将二者交换位置，这叫向上调整（AdjustUp）接下来将给出实现

void HeapPush(HP* php, HPDataType x) {
    assert(php);
    if (php->size == php->capacity) {
        int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;        //这种实现方法类似于队列
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}  

4.向上调整(AdjustUp)

大家需要记住的是，根节点位置=。找到父子节点的位置就可以开始交换（Swap），这个函数我们会在下面实现

void AdjustUp(HPDataType* a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] < a[parent]) {
            Swap(&a[child], &a[parent]);//传址调用
            child = parent;//child用来记录插入节点的位置
            parent = (child - 1) / 2;
        }
        else {
            break;
        }
    }
}  

5.交换节点(Swap)

特别注意这里用到传址调用，这样才可以改变原数组中数据。

void Swap(HPDataType* p1, HPDataType* p2) {
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}  

6.出堆(HeapPop)

大家可能认为堆的删除像链表一样删掉最后一个元素就行了。但是我们要知道堆的终极目的，在堆顶的元素一定是最大的或者最小的，那么出堆提取出堆顶元素才让我们这个数据结构有意义（堆排序）在堆顶出去之后，是将原数组按位往前移动吗？当然不是，这样操作会改变堆原来的关系，会让你的叔叔当你的兄弟，你的兄弟当你的儿子。所以我们将最后一个节点的元素移动到栈顶，然后将其向下调整（AdjustDown）就可以了。

void HeapPop(HP* php) {
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}  

7.向下调整(AdjustDown)

这里要知道 左孩子节点=父节点2+1 右孩子节点=父节点2+2

void AdjustDown(HPDataType* a, int size, int parent) {
    int child = parent * +1;
    while (child < size) {
        if (child + 1 < size && a[child + 1] < a[child]) {
            ++child;
        }
        if (a[child < a[parent]]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}  

8.返回堆顶元素(HeapTop)

HPDataType HeapTop(HP* php) {
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}  

9.返回堆元素个数(HeapSize)

size_t HeapSize(HP* php) {
    assert(php);
    return php->size;
}  

10.判断堆是否为空(HeapEmpty)

bool HeapEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}  

三、总结

在上文中我们学习了堆的建立，那么建堆会有两种办法，分别是向上调整和向下调整，但是两种方法的时间复杂度不同，我们在后面的文章里会讲解两种方法建堆的时间复杂度。