堆的实现以及利用堆进行排序

发布于：2025-04-19 ⋅ 阅读:(47) ⋅ 点赞:(0)

堆

堆的实现

在数据结构中，堆是一种非常重要的结构，尤其在需要频繁访问最大值或最小值的场景中。今天，我们将通过C语言实现一个最小堆，并详细介绍其核心功能和实现细节。最大堆的实现只需通过改变向上向下调整的大于小于号即可

1. 什么是堆？

堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最小堆中，父节点的值总是小于或等于其子节点的值。这种特性使得堆的根节点始终是所有节点中的最小值，非常适合实现优先队列。
在这里插入图片描述
堆有以下的性质：

  1. 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
  2. 堆总是⼀棵完全⼆叉树。

⼆叉树性质

  1. 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：

  2. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点

  3. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦

  4. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

2. 最小堆的核心操作

最小堆的基本操作包括初始化、插入、删除、获取堆顶元素、判断堆是否为空等。以下是这些操作的具体实现：

2.1 初始化堆

初始化堆时，我们需要为堆分配一个动态数组，并设置其容量和大小。

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

2.2 销毁堆

销毁堆时，需要释放动态分配的内存，并将堆的指针和容量、大小重置为初始状态。

void HeapDestroy(Heap* hp)
{
    if (!hp) return;
    if (hp->a)
        free(hp->a);
    hp->a = NULL;
    hp->capacity = hp->size = 0;
}

2.3 插入元素

插入元素时，首先检查堆的容量是否已满。如果已满，则动态扩展容量。插入后，通过向上调整（AdjustUp）确保堆的性质。

int HeapPush(Heap* php, HPDataType x)
{
    assert(php);
    if (php->capacity == php->size)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL)
            return -1;
        php->a = tmp;
    }
    php->a[php->size] = x;
    AdjustUp(php->a, php->size);
    php->size++;
    return 0;
}

2.4 删除堆顶元素

删除堆顶元素时，将堆顶元素与最后一个元素交换，然后减少堆的大小，并通过向下调整（AdjustDown）确保堆的性质。

void HeapPop(Heap* hp)
{
    assert(!HeapEmpty(hp));
    Swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;
    AdjustDown(hp->a, 0, hp->size);
}

2.5 获取堆顶元素

堆顶元素即为堆的根节点，可以直接返回。

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    return hp->a[0];
}

2.6 判断堆是否为空

通过检查堆的大小是否为零来判断堆是否为空。

bool HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->size == 0;
}

3. 调整堆的算法

堆的调整是实现堆操作的核心。向上调整（AdjustUp）和向下调整（AdjustDown）分别用于插入和删除操作。

3.1 向上调整

向上调整算法

• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后

• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
向上调整用于插入操作。从插入的节点开始，逐层向上比较和交换，直到满足堆的性质。

void AdjustUp(HPDataType* arr, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (arr[child] < arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

3.2 向下调整

向下调整算法

• 将堆顶元素与堆中最后⼀个元素进⾏交换

• 删除堆中最后⼀个元素

• 将堆顶元素向下调整到满⾜堆特性为⽌

向下调整用于删除操作。从根节点开始，逐层向下比较和交换，直到满足堆的性质。

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

4. 测试代码

以下是测试代码，用于验证堆的功能：

int main()
{
    Heap hp;
    HeapInit(&hp);

    HeapPush(&hp, 5);
    HeapPush(&hp, 3);
    HeapPush(&hp, 8);
    HeapPush(&hp, 2);

    printf("HeapTop: %d\n", HeapTop(&hp)); // 输出 2
    printf("HeapSize: %d\n", HeapSize(&hp)); // 输出 4

    HeapPop(&hp);
    printf("HeapTop after pop: %d\n", HeapTop(&hp)); // 输出 3

    HeapDestroy(&hp);
    return 0;
}

堆排序

堆排序时通常排的是升序，需改变adjust down的大于小于号，使其排最大堆；

一.向下调整建堆

  1. 构建最大堆：
    初始时，数组是无序的，需要将其构建成一个最小堆。
    从最后一个非叶子节点开始（索引为 (n - 1 - 1) / 2），逐个向上调整，确保每个子树都满足最大堆的性质。
    调整完成后，数组的前半部分形成了一个最小堆。
  2. 排序过程：
    每次将堆顶元素（最大值）与堆的最后一个元素交换，这样最大值就放到了数组的末尾。
    然后缩小堆的范围（end–），并重新调整堆，确保剩余部分仍然是一个最小堆。
    重复上述过程，直到堆中只剩下一个元素，此时数组已经完全排序
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}

二.向上调整建堆

  1. （一）向上调整（AdjustUp）
    向上调整是用于在插入新元素时，将元素调整到合适的位置，以保持堆的性质。其步骤如下：
    比较当前节点与其父节点的值。
    如果当前节点的值大于父节点的值（最大堆），则交换它们的位置。
    更新当前节点为父节点，重复上述步骤，直到当前节点的值小于父节点的值，或者当前节点已经是根节点。
  2. （二）向下调整（AdjustDown）
    向下调整是用于在删除堆顶元素后，将堆重新调整为最大堆。其步骤如下：
    比较当前节点与其子节点的值。
    如果子节点的值大于当前节点的值（最大堆），则交换它们的位置。
    更新当前节点为子节点，重复上述步骤，直到当前节点的值大于其子节点的值，或者当前节点已经是叶子节点。
  3. （三）堆排序的完整过程
    构建最大堆：从最后一个非叶子节点开始，逐个向上调整，直到根节点。

排序：

  1. 交换堆顶元素和最后一个元素。
  2. 对剩余的堆重新调整，使其满足最大堆的性质。
  3. 重复上述步骤，直到堆的大小为1。
void HeapSort1(int* a, int n) {
    // 构建最大堆
    for (int i = 0; i < n; i++) {
        AdjustUp(a, i);
    }

   //排序过程
    int end = n - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]); // 交换堆顶和最后一个元素
        AdjustDown(a, 0, end); // 重新调整堆
        end--;
    }
}

在日常使用堆排序时，一般使用向下建堆，因为在考虑时间复杂度时，向下建堆要小于向上建堆。
在这里插入图片描述

时间复杂度分析

向上建堆分析：

第1层，0个结点，需要向上移动0层
第2层，2个结点，需要向上移动1层
第3层，4个结点，需要向上移动2层
第4层，8个结点，需要向上移动3层
…
第h层，2的h次个结点，需要向上移动h-1层
在这里插入图片描述

向下建堆分析

分析：
第1层，0个结点，需要向下移动h-1层
第2层， 2个结点，需要向下移动h-2层
第3层， 4个结点，需要向下移动h-3层
第4层，8个结点，需要向下移动h-4层
…
第h-1层，2 个结点，需要向下移动1层
到这里为止，就可以大略的看出其实向下建堆时间复炸度其实是要小的。
下面给出数学分析：
在这里插入图片描述

总结

通过上述代码，我们实现了一个功能完整的最小堆。堆的核心操作包括初始化、插入、删除、获取堆顶元素等。通过向上调整和向下调整算法，我们确保了堆的性质始终得以维护。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布