当前位置：首页 > news >正文

二叉树(中)-- 堆

news 来源：原创 2025/9/11 19:28:58

堆是一个独立的数据结构，堆是一个二叉树。堆和栈几乎没有什么关联

堆是一个完全二叉树，可以用数组存储

大堆：任何一个父亲都大于等于孩子
小堆：任何一个父亲都小于等于孩子

请注意，小堆大堆并不一定是升序或降序，同级的兄弟之间并没有明确的大小关系

堆的意义：可以做堆排序（Top K问题）等等

特点：

根是最小或者最大
效率很高

堆的定义

我们来看一下一个堆的定义

堆逻辑上是一个二叉树，有父子关系啊层级关系，但是在物理上是一个数组，存储着一些数

所以我们在创建的时候要按着物理层面去创建，但是心中要想到他的逻辑图

typedef int HPDataType;
typedef struct Heap {HPDataType* a;  //数组int size;  //元素个数int capacity;  //空间大小
}HP;

堆的初始化和销毁显而易见，和顺序表一致

//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}
//堆的销毁
void HPDestory(HP* php)
{assert(php);free(php->a);php->capacity = php->size = 0;                                                                                                                                                                                                                     
}

堆的插入

我们以小堆为例

堆的插入逻辑如下：

如果是小堆，则将待插入的数据先放在最后，然后与其父节点进行比较，如果比父节点小就与父节点交换位置

如果不能理解可以这么想假设父节点是 a，有一个已知的子节点 b ，现在有待插入节点 c ，a < b 且 a > c 则 a 与 c 进行交换，c < a 且 c < b ,c 是 a 和 b 的父节点符合小堆的定义然后再继续往上一级比较，也就是和自己所有的祖先进行比较

//向上调整
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
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;parent = (child - 1) / 2;}elsebreak;}
}
void HPPush(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 failed");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;//向上调整AdjustUp(php->a, php->size - 1);    //我们计算父子关系用的下标来计算
}

上图便是向上调整的图解方法

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;parent = (child - 1) / 2;}elsebreak;}
}

在向上调整函数 AdjustUp中，while 循环的结束条件child = 0 的时候，也就是插入的节点来到了根节点处。

那把结束条件改成 parent < 0 呢，我们知道当parent 到 0 的时候也算到了根节点处，但是数组没有负数下标，在 parent = (child - 1) / 2 中怎么除也不会小于 0 ，巧合地是当 parent = 0 时且 child = 0 时，a[child] = a[parent] ，不符合判断条件，直接break，也完成了插入。所以两种方法都可以，但是最好用 child > 0 作为判断

建堆

有了插入，我们现在就可以来建堆了，只需要将数组中的元素依次插入即可

int main()
{HP a;int arr[8] = { 2, 3 ,5, 7 ,9 ,1 ,10, 4 };HPInit(&a);for (size_t i = 0; i < sizeof(arr) / sizeof(int); i++){HPPush(&a, arr[i]);}return 0;
}

该函数会自动调整是元素满足堆的排列规则

堆的删除

关于堆的删除，我们并不是删除其在物理层面的最后一个元素而是将根节点删除

我们不能使用挪动覆盖删除堆顶的数据，直接覆盖会导致堆中的关系大乱，兄弟变父子，父子变兄弟

我们可以先将物理层面数组的第一个数据和最后一个数据先互换，再删除最后一个数据，也就是一开始的根节点被删除了，但是此时根节点与其子节点的关系出现问题，此时就需要使用向下调整算法

pop 一次后我们发现一个有趣的事情，此时的根节点是现在最小的那个数，比之前删除的那个数大，所以每次删除都会有序取出堆中最小的数，如果全部 pop 并依次排列便会形成一个有序的升序数列，看似无序的堆变得有序了起来

如何判断向下调整到了叶节点呢，我们只需要判断其是否存在左孩子即可，如果乘二加一后其下标已经超过数组了，则不存在左孩子也就是到达叶节点了

如果想改成大堆的话，就把向上调整和向下调整的大小关系换一下就行了

//删除堆顶的数据（根位置）
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child])  //要防止越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void HPPop(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);
}

向下调整算法的三个参数分别是数组元素总个数当前待向下调整的节点所在数组的下标

取堆顶元素

//返回堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

判空

//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

打印最小的 n 个数

当我们有了插入函数和删除函数与取堆顶函数之后，我们便可以打印出1堆数字中最小的 n 个数

#include "Heap.h"int main()
{HP a;int arr[] = { 2, 3 ,5, 7 ,9 ,1 ,10, 4 };HPInit(&a);for (size_t i = 0; i < sizeof(arr) / sizeof(int); i++){HPPush(&a, arr[i]);}//打印有序while (!HPEmpty(&a)){printf("%d ", HPTop(&a));HPPop(&a);}return 0;
}

现在只能是打印排序而没有真正影响到堆的排序，但也是堆排序的前生

如果想实现真正的排序，且让空间复杂度尽量小，我们不能专门建一个堆，这样太烦了，所以我们可以直接使用向上调整函数，把一个数组当成完全二叉树

void HeapSort(int* a, int n)
{//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}
}

这样就直接将一个数组变成小堆了

需要提醒的是堆的物理和逻辑层，我们在删除的时候，并不是真正的删除，只是逻辑上的将最后一个元素排除在堆外，但物理上他仍然在数组中，我们要综合两个方面取思考不能完全被逻辑图糊弄

想变成降序，就建小堆

首先我们变成小堆后，根节点就是最小的一个，模仿删除函数，我们将首和尾换位置后删除，此时最后一个便是最小的

多次进行同样的操作我们便可以形成降序数列

//降序排列
void HeapSort(int* a, int n)
{//建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

所以这里排序的关键就是这两个向上调整和向下调整算法

其时间复杂度为 O(N * log N) 算是比较快的排序算法了

这个时候，我们想一个问题，建堆有没有更快的方法呢？向下调整算法的前提是其子树也按大堆排列的，那么同理子节点的子树也要大堆排列，很麻烦。既然对于向下调整算法是要求下面都是大堆，我们不如从下往上来进行向下调整算法。对于叶子节点，其既是大堆又是小堆，不用管，所以从倒数第一个非叶子节点开始向下调整

这个建堆算法更快，写法差不多

void HeapSort(int* a, int n)
{//建堆
//    for (int i = 1; i < n; i++)
//    {
//        AdjustUp(a, i);
//    }for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
}

所以说，向上调整算法可以让随意一个数组变成大小堆，向下调整算法要其子树是小堆才能全变成小堆，子树是大堆才能变成大堆。

堆的定义

堆的插入

建堆

堆的删除

取堆顶元素

判空

打印最小的 n 个数

相关文章：