【数据结构】堆的基本实现

【数据结构】堆的基本实现

引用

CSDN

1.

https://blog.csdn.net/tuweizhiwang/article/details/138804671

堆是数据结构中一种重要的数据结构，它本质上是一个数组实现的优先级队列，同时表示成一颗完全二叉树。本文将详细介绍堆的基本概念、结构以及各种基本功能的实现方法，包括初始化、销毁、打印、向上调整、插入、向下调整、删除、判断是否为空、取堆顶数据和获取有效数据个数等。

1、堆的概念和结构

首先说明：这里的堆是数据结构里面的堆，并不是操作系统里的堆区

堆本质上是数组实现优先级队列功能，但是表示成一颗完全二叉树，物理上是数组，逻辑上是完全二叉树，前
n-1
层满节点，最后一层从左到右连续

堆分为两种情况，最大堆（大根堆）和最小堆（小根堆）

• 最大堆：所有的父节点都大于等于子节点，说明堆顶就是最大值。
• 最小堆：所有的父节点都小于等于子节点，说明堆顶就是最小值。

2、堆基本功能实现

堆是本质是数组的优先级队列，表示成完全二叉树，物理结构是数组，逻辑结构是完全二叉树

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}Heap;
// 初始化
void HeapInit(Heap* ph);
// 销毁
void HeapDestroy(Heap* ph);
// 打印
void HeapPrint(Heap* ph);
// 交换
void Swap(HPDataType* pa, HPDataType* pb);
// 向上调整
void AdjustUp(Heap* ph, int child);
// 插入
void HeapPush(Heap* ph, HPDataType x);
// 向下调整
void AdjustDown(Heap* ph, int parent);
// 删除
void HeapPop(Heap* ph);
// 取堆顶数据
void HeapTop(Heap* ph);
// 堆是否为空
bool HeapEmpty(Heap* ph);
// 堆的有效个数
int HeapSize(Heap* ph);

2.1 初始化和销毁

// 初始化
void HeapInit(Heap* ph)
{
    assert(ph);
    ph->a = NULL;
    ph->size = ph->capacity = 0;
}
// 销毁
void HeapDestroy(Heap* ph)
{
    assert(ph);
    free(ph->a);
    ph->size = ph->capacity = 0;
}

2.2 打印

由于是堆的性质是队列，本质上是个数组，但是队列通常不能打印，我这里是为了方便查看数据才实现。

// 打印
void HeapPrint(Heap* ph)
{
    for (int i = 0; i < ph->size; i++)
    {
        printf("%d ", ph->a[i]);
    }
    printf("\n");
}

2.3 向上调整

思路：

1. 以小根堆为例，所有的
   parent <= child
2. 找到需要调整的子节点的父亲，
   parent = (child - 1) / 2
3. parent的值比child要大，需要交换值，把新的child置为现在parent，新的parent在用新的child计算得来
4. 调整完毕分两种情况：

• 重复步骤3，直到child > 0，这里说明child == 0，就是根节点，不用在调整
• parent <= child，说明当前堆结构是正常的，不用调整

// 向上调整
// 小堆：所有的父亲要小于等于孩子
void AdjustUp(Heap* ph, int child)
{
    assert(ph);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        // 父亲的值大于孩子，需要调整
        if (ph->a[child] < ph->a[parent])
        {
            Swap(&ph->a[child], &ph->a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            // 堆结构正常
            break;
        }
    }
}

2.4 插入

插入的逻辑还是和顺序表类似，但是在最后多了一个向上调整，这也是最关键的，大家可以看动图
这里以小根堆结构为例，插入的逻辑还是和顺序表类似，但是在最后多了一个向上调整，这也是最关键的。
因为堆的特性，插入数据后还是需要保持小根堆的结构，正常在后面插入就会破坏堆原有的结构，所以我们插入完数据就需要向上调整，保持堆的特性。

// 插入，建堆
void HeapPush(Heap* ph, HPDataType x)
{
    assert(ph);
    // 容量检查和扩容
    if (ph->size == ph->capacity)
    {
        int newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(ph->a, newCapacity * sizeof(HPDataType));
        assert(tmp);
        ph->a = tmp;
        ph->capacity = newCapacity;
    }
    // 插入数据
    ph->a[ph->size] = x;
    ph->size++;
    // 插入新数据后，堆的结构会被破坏，从最后一个数据开始向上调整
    AdjustUp(ph, ph->size - 1);
}

2.5 向下调整

思路：

1. 以小根堆为例，所有的
   parent <= child
2. 算出调整的节点的子节点，leftchild = parent * 2 +1
3. 求出左右子节点哪个更小，要注意可能右子节点不存在的情况，防止越界
4. 拿小的子节点和父亲比较，parent > child就交换，新的parent置为现在的child，新的child通过新的parent计算出来
5. 调整完毕分两种情况：

• 重复步骤3、4，直到child < size，说明父亲节点在叶子结点，没有孩子，不能调整，否则会越界
• parent <= child，说明当前堆结构是正常的，不用调整

// 向下调整
void AdjustDown(Heap* ph, int parent)
{
    assert(ph);
    int child = parent * 2 + 1;
    // 调整到叶子结点结束
    while (child < ph->size)
    {
        // 防止越界：右孩子可能不存在
        // 求出左右子节点哪个更小
        if (child + 1 < ph->size && ph->a[child] > ph->a[child + 1])
        {
            child++;
        }
        // 父亲比子节点大，就交换
        if (ph->a[parent] > ph->a[child])
        {
            Swap(&ph->a[child], &ph->a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            // 堆结构正常
            break;
        }
    }
}

2.6 删除

由于队列的特性，我们删除堆顶的数据，就会破坏堆原有的结构。
所以需要让堆顶和最后数据交换，size–，就等于删除了原来的栈顶数据相当于出栈
我们在让栈顶向下调整，就可以让堆结构正常

// 删除
void HeapPop(Heap* ph)
{
    assert(ph);
    // 空堆不能删除
    assert(!HeapEmpty(ph));
    
    // 交换
    Swap(&ph->a[0], &ph->a[ph->size - 1]);
    ph->size--;
    // 交换后，堆的结构会被破坏，从堆顶开始向下调整让结构正常
    AdjustDown(ph, 0);
}

2.7 堆判断是否为空

// 堆是否为空
bool HeapEmpty(Heap* ph)
{
    assert(ph);
    return ph->size == 0;
}

2.8 取堆顶数据

// 取堆顶数据
void HeapTop(Heap* ph)
{
    assert(ph);
    // 空堆不能取
    assert(!HeapEmpty(ph));
    return ph->a[0];
}

2.9 堆的有效数据

// 堆的有效个数
int HeapSize(Heap* ph)
{
    assert(ph);
    return ph->size;
}

3、功能测试

将乱序数据插入到堆中，打印看是否堆的结构
很明显结构是正常的小堆
删除两个数据，堆结构是否还是正常呢
依旧符合堆的结构，同时也是队列的性质先进先出，数据1和4出队了

4、总结

学好堆的关键就是对向下调整和向上调整的理解，并灵活运用。