一、介绍

• 这里的堆，其实是一种数据结构，是将数据按完全二叉树的顺序存储方式存储在一个一维数组中，称为堆
• 如果堆中父节点小于子节点的值，则叫做小堆，其根节点的值是整个堆中最小的
• 如果堆中父节点大于子节点的值，则叫做大堆，其根节点的值是整个堆中最大的
• 堆总是一个完全二叉树，因此操作过程中要保证堆的结构

这就是一个以$9,7,8,6,4,5,3,2,0,1$顺序存储的大堆

二、大（小）堆的实现

typedef int HPDataType;
//堆的数据结构
typedef struct Heap
{HPDataType* a;int size;//元素个数int capacity;//容量
}HP;

1. 堆的初始化

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

2. 堆的销毁

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

3. 添加元素

示例：添加10

首先在数组尾添加10，然后在依次向上调整，保证大堆结构。

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, sizeof(HPDataType)*newcapacity);if (tmp == NULL)//扩容失败{printf("realloc fail\\n");exit(-1);}php->a = tmp;php->capacity = newcapacity;}//在堆尾（下标为size）处插入xphp->a[php->size] = x;php->size++;//元素个数加1//调整堆，使其满足大（小）堆AdjustUp(php->a, php->size - 1);
}

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;}else{break;}}
}

4. 删除堆顶元素

示例：删除10

为了使大堆的结构不乱，不能直接删除根节点10，需要先与尾节点4交互，然后在删除尾结点10，在将根节点4向下调整，保持结构。

void HeapPop(HP* php)
{assert(php);//堆中需要有元素assert(php->size > 0);//将堆顶和堆尾元素交换Swap(&(php->a[0]), &(php->a[php->size - 1]));php->size--;//元素个数减1//调整堆，使其满足大（小）堆AdjustDwon(php->a, php->size, 0);
}

只是将元素个数减一，来达到删除的效果，实际上并没删除

void AdjustDwon(HPDataType* a, int size, int parent)
{//先计算出左孩子的下标int child = parent * 2 + 1;//通过size来限定调整的范围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;}}	
}

5.取出堆顶元素

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);//即数组中第一个元素return php->a[0];
}

三、⭐堆排序

1.问题

通过堆的算法，实现对数据排序

2. 思路

• 首先将需要排序的数据，如数组，转化成大（小）堆
• 利用大（小）堆的特点——根节点的值是整个数据中最大（小）的
• 如果是排升序，建立大堆。然后每次把根节点拿出来放到堆尾，这样数据中元素就是由小到大排列了
• 如果是排降序，建立小堆。然后每次把根节点拿出来放到堆尾

3. 代码

void HeapSort(int* a, int n)
{/*从最后一个节点（下标n-1）的父节点（下标(n-1-1)/2）开始依次向上（--i）进行向下调整，建立大堆*/for (int i = (n-1-1)/2; i >= 0; --i){AdjustDwon(a, n, i);}int size = n;while (size > 0){Swap(&a[0], &a[--size]);//每次从根节点（0），开始每次调整n--个数据的堆。AdjustDwon(a, size, 0);}
}

4.🪄 时间复杂度

4.1 向下建堆的时间复杂度：

示例：对有n个节点的堆

则建堆需要交互的次数为：
T(n)=20×(h−1)+21×(h−2)+22×(h−3)+...+2h−2×1T(n)=2^0\\times(h-1)+2^1\\times(h-2)+2^2\\times(h-3)+...+2^{h-2}\\times1 T(n)=20×(h−1)+21×(h−2)+22×(h−3)+...+2h−2×1
利用错位相减法:
2∗T(n)=21×(h−1)+22×(h−2)+...+2h−2×2+2h−1×1两式相减:T(n)=21+22+23+...+2h−1−(h−1)=1+21+22+23+...+2h−1−h=1×2h−12−1−h=2h−1−h2*T(n) = 2^1\\times(h-1)+2^2\\times(h-2)+...+2^{h-2}\\times2+2^{h-1}\\times1 \\\\两式相减:\\\\ T(n) = 2^1+2^2+2^3+...+2^{h-1}-(h-1)\\\\ =1+2^1+2^2+2^3+...+2^{h-1}-h\\\\ =1\\times\\frac{2^{h}-1}{2-1}-h\\\\ =2^h-1-h 2∗T(n)=21×(h−1)+22×(h−2)+...+2h−2×2+2h−1×1两式相减:T(n)=21+22+23+...+2h−1−(h−1)=1+21+22+23+...+2h−1−h=1×2−12h−1​−h=2h−1−h
其中
n=2h−1h=log2(n+1)则T(n)=n−log2(n+1)≈nn=2^h-1 \\quad h=log_2(n+1)\\\\则\\\\T(n) = n-log_2(n+1)\\approx n n=2h−1h=log2​(n+1)则T(n)=n−log2​(n+1)≈n

4.2 开始排序的时间复杂度：

int size = n;
while (size > 0)
{Swap(&a[0], &a[--size]);//每次从根节点（0），开始每次调整n--个数据的堆。AdjustDwon(a, size, 0);
}

每次交换第一个和最后一个，将数组的个数$-1$，然后将交换上来的根节点向下调整，其最多交换log2(n−1)log_2(n-1)log2​(n−1)次(深度)。

循环$n-1$次，其时间复杂度大约为T(n)≈n×log2nT(n) \\approx n \\times log_2nT(n)≈n×log2​n

对于整个堆排序，其时间复杂度约为：O(nlog2n)O(nlog_2n)O(nlog2​n)

四、🌟TOP-K问题

1. 问题

在有n个元素的数据中，找出前$k$个最大（小）的元素（一般n是远大于k的）

2. 思路

这里根据堆，提供三种思路：

1. 堆排序，见上文，可以取出排序好的前k个元素

2. 建一个$n$个空间的堆，然后一次取出$k$次（Top&Pop）
   时间复杂度O(n+klog2n)O(n+klog_2n)O(n+klog2​n)，空间复杂度为$O(n)O(n)$.

3. 先取$k$个元素，建成大（小）堆，如果是要求前$k$个最大的元素，建小堆，然后将剩下的元素与堆顶元素进行比较，如果大于堆顶，则替换堆顶元素，然后再调整，到遍历结束，小堆中的$k$个元素就是整个数据中的前$k$个最大元素了。

   时间复杂度为O(k+(n−k)log2k)O(k+(n-k)log_2k)O(k+(n−k)log2​k)，空间复杂度为$O(k)$.

3. 代码

对于思路3，代码如下：（需要注意AdjustDwon()，前K个最大的–>建小堆)。

void PrintTopK(int* a, int n, int k)
{assert(a&&n&&k);//用a中前k个元素建堆int* myHeap = (int*)malloc(sizeof(int)*k);assert(myHeap);for (int i = 0; i < k; ++i){myHeap[i] = a[i];}for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDwon(myHeap, k, i);}//将剩余n-k个元素依次与堆顶元素交换，不满则则替换for (int j = k; j < n; ++j){if (a[j] > myHeap[0]){myHeap[0] = a[j];AdjustDwon(myHeap, k, 0);}}//输出小堆中元素for (int i = 0; i < k; ++i){printf("%d ", myHeap[i]);}printf("\\n");
}

🦀🦀观看~

XP系统