利用C语言模拟实现堆的基本操作和调堆算法

文章目录

利用C语言模拟实现堆的基本操作和调堆算法
- 前言
- 一、堆的基本原理
- - 大根堆和小根堆的比较
- 二、实现堆的基本操作
- - 1）结构定义
  - 2）初始化堆（HeapInit）
  - 3）销毁堆（HeapDestroy）
  - 4）堆的调整算法
  - - （1）向上调堆算法
    - （2）向下调堆算法
  - 5）堆的插入操作（HeapPush）
  - 6）堆的删除操作（HeapPop）
  - 7）获取堆顶元素（HeapTop）
  - 8）获取堆的大小（HeapSize）
  - 9）判断堆是否为空（HeapEmpty）
  - 10）打印堆（HeapPrint）
- 三、测试堆的功能
- 总结

前言

堆是一种重要而高效的数据结构，广泛应用于各种算法和数据处理场景。本篇博客将介绍如何使用C语言模拟实现堆的基本操作，包括初始化、插入、删除等，并通过回调函数和函数指针的灵活运用，实现大根堆和小根堆的不同调堆算法。

一、堆的基本原理

堆是一种特殊的树形数据结构，具有以下基本特点：

完全二叉树的结构，即除了最底层，其他层都是满的。
堆中的每个节点的值都必须大于等于或小于等于其子节点的值，根据此条件分为大根堆和小根堆。

堆常被用来实现优先队列等数据结构，其中最值的快速访问是堆的主要优势。

大根堆和小根堆的比较

大根堆和小根堆的不同之处在于调堆算法中的比较条件。在大根堆中，父节点的值必须大于子节点的值；而在小根堆中，父节点的值必须小于子节点的值。通过函数指针，我们可以根据用户的选择动态切换调堆算法，使代码更加灵活。

二、实现堆的基本操作

声明： 此处采用动态数组模拟实现堆（完全二叉树）

1）结构定义

定义了堆的结构，包括元素数组、大小、容量和标识是大根堆还是小根堆的字符。

typedef int HPDataType;

typedef struct Heap {
    HPDataType* a;
    size_t size;
    size_t capacity;
    char RootBigOrSmall;
} HP;

2）初始化堆（HeapInit）

通过 HeapInit 函数初始化堆结构，用户可以选择大根堆（‘B’或’b’）或小根堆（‘S’或’s’）。

void HeapInit(HP* php)
{
    assert(php);

    printf("请挑选大根堆（big -> B）或小根堆（small -> S）: 【输入首字母大小写】");
    char choose = ' ';
    choose = getchar();
    if (choose == 'B' || choose == 'S' || choose == 'b' || choose == 's') { php->RootBigOrSmall = choose; }
    else { printf("输入有误！"); return; }

    php->a = NULL;
    php->capacity = php->size = 0;
}

3）销毁堆（HeapDestroy）

释放堆内存和相关资源的 HeapDestroy 函数。

void HeapDestroy(HP* php)
{
    assert(php);

    free(php->a);
    php->a = NULL;
    php->capacity = php->size = 0;
}

4）堆的调整算法

（1）向上调堆算法

void adjustUpHeap(HPDataType* a, size_t child, bool (*cmp)(HPDataType _parent, HPDataType _child))
{
    size_t parent = (child - 1) / 2;
    if (child == 0) { parent = 0; }

    while (child > 0)
    {
        if (cmp(a[parent], a[child]))
        {
            HPDataType tmp = a[parent];
            a[parent] = a[child];
            a[child] = tmp;
        }

        child = parent;
        parent = (parent - 1) / 2;
    }
}

（2）向下调堆算法

void adjustDownHeap(HPDataType* a, HPDataType size, HPDataType parent,
    bool (*cmp)(HPDataType _parent, HPDataType _child))
{
    HPDataType child = parent * 2 + 1;

    while (child < size)
    {
        if (child + 1 < size && cmp(a[child], a[child + 1]))
        {
            child++;
        }

        if (cmp(a[parent], a[child]))
        {
            HPDataType tmp = a[parent];
            a[parent] = a[child];
            a[child] = tmp;
            parent = child;
            child = child * 2 + 1;
        }
        else { break; }
    }
}

这里采用函数指针作为两种调堆算法的参数是因为通过此方法可实现运行后指定大根堆或小根堆从而影响相关控制堆的操作，比如 HeapPush和 HeapPop等操作。

5）堆的插入操作（HeapPush）

通过 HeapPush 函数插入元素，并通过向上调堆算法保持堆的性质。

void HeapPush(HP* php, HPDataType x)
{
    assert(php);

    // 检查扩容
    if (php->capacity == php->size)
    {
        size_t new_capacity = (php->capacity == 0 ? 4 : php->capacity * 2);
        HPDataType* tmp = (HPDataType*)realloc(php->a, new_capacity * sizeof(HPDataType));
        if (!tmp) { perror("realloc of HeapPush"); return; }

        php->a = tmp;
        php->capacity = new_capacity;
    }

    php->a[php->size++] = x;

    // 调堆
    bool (*cmp)(HPDataType _parent, HPDataType _child) = NULL;
    if (php->RootBigOrSmall == 'B' || php->RootBigOrSmall == 'b')
    {
        cmp = bigRootHeap_cmp;
    }
    else
    {
        cmp = smallRootHeap_cmp;
    }
    adjustUpHeap(php->a, php->size - 1, cmp);
}

注意： 这里使用动态数组存储堆的节点，所以需要考虑空间扩容问题，当容量不足时利用 realloc() 函数从堆区申请额外空间。

6）堆的删除操作（HeapPop）

通过 HeapPop 函数删除堆顶元素，并通过调堆算法保持堆的性质。

void HeapPop(HP* php)
{
    assert(php);
    assert(php->a && php->size > 0);

    bool (*cmp)(HPDataType _parent, HPDataType _child) = NULL;
    if (php->RootBigOrSmall == 'B' || php->RootBigOrSmall == 'b')
    {
        cmp = bigRootHeap_cmp;
    }
    else
    {
        cmp = smallRootHeap_cmp;
    }

    // 去顶节点
    HPDataType tmp = php->a[0];
    php->a[0] = php->a[php->size - 1];
    php->a[php->size - 1] = tmp;
    php->size--;

    // 调堆
    adjustDownHeap(php->a, php->size, 0, cmp);
}

7）获取堆顶元素（HeapTop）

通过 HeapTop 函数获取堆顶元素。

HPDataType HeapTop(const HP* php)
{
    assert(php);
    assert(php->a && php->size > 0);

    return php->a[0];
}

8）获取堆的大小（HeapSize）

通过 HeapSize 函数获取堆的大小。

size_t HeapSize(const HP* php)
{
    assert(php);

    return php->size;
}

9）判断堆是否为空（HeapEmpty）

通过 HeapEmpty 函数判断堆是否为空。

bool HeapEmpty(const HP* php)
{
    assert(php);

    return php->size == 0;
}

10）打印堆（HeapPrint）

通过 HeapPrint 函数输出堆的内容。（测试时避免代码冗杂）

void HeapPrint(const HP* php)
{
    assert(php);

    for (int i = 0; i < php->size; i++)
    {
        std::cout << php->a[i] << '\t';
    }
    std::cout << "\n";
}

三、测试堆的功能

测试代码：

int main()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 15);
	HeapPush(&hp, 18);
	HeapPush(&hp, 19);
	HeapPush(&hp, 25);
	HeapPush(&hp, 28);
	HeapPush(&hp, 34);
	HeapPush(&hp, 65);
	HeapPush(&hp, 49);
	HeapPush(&hp, 27);
	HeapPush(&hp, 37);

	HeapPrint(&hp);

	HeapPush(&hp, 30);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapDestroy(&hp);

	return 0;
}