1.堆的本质：完全二叉树
堆在物理结构上是顺序结构，实现方式类似于顺序表（数组）；但在逻辑结构上是树形结构，准确来说堆是一棵完全二叉树。因为堆的实现在代码上和顺序表有很高的相似度，所以在写代码时，我们要仔细理解堆的逻辑结构，理解每步操作对该二叉树的影响，我们也可以画画简图，更加直观地感受堆的相关操作的含义。
2.向上调整与向下调整使用场景
当数据插入堆或从堆顶移除后，都要对堆进行相关的调整，使其成为一个新堆。调整方式分为向上调整和向下调整，它们有不同应用场景：
①向上调整：尾部插入数据时使用。当在尾部加入一个新的数据时，这个数据可能要和父节点交换后才能形成大（小）堆，交换过程中除了新插入的节点可能不满足堆的规则以外，其余节点都不需要调整。
函数参数参考：void AdjustUp(HPDataType* arr, int child);
下面举个例子：
对于这个小堆，这里新插入了一个0，需要进行调整，我们这时选择向上调整，即沿着祖先向上调整，其余部分不调整
②向下调整：当数据从堆顶移除或建堆时使用。
函数参数参考：void AdjustDown(HPDataType* arr, int size, int parent);
a.从堆顶移除数据时向下调整：先交换首元素和尾元素，并用顺序表的方式让size--，使得最后一个元素被删除，再向下调整直到成堆
b.建堆：建堆一般来说有两种方式，一种是向上调整，每次新插入一个元素后向上调整直到成堆；另一种是向下调整，在加入所有数据后从倒数第二行开始向下调整直到成堆。一般来说，我们采用向下调整，因为对于建堆而言，向下调整的时间复杂度近似为O(N-logN)或O(N)，而向上调整的时间复杂度为O(NlogN)，下面简单讲解一下：
向上调整建堆：共有N个元素，每次向上调整logN次，时间复杂度O(logN)
向下调整建堆：第一眼看上去虽然也是O(NlogN)，但多观察就发现调整次数远远小于向上调整
经过详细计算可知比较准确的时间复杂度是O(N-logN)，可以再近似于O(N)，但我们不用特别纠结于如何精确计算时间复杂度，而是要像上面两张图那样学会粗略地分析和计算
3.堆排序：如果一来就学习堆排序的话，其实会很困难，但如果学会了堆的相关操作，掌握向上和向下调整之后，堆排序就非常简单了。
我们需要用到的知识点就只有：(子节点-1) / 2 == 父节点，父节点 * 2 + 1 == 左孩子结点，父节点 * 2 + 2 == 右孩子结点，堆删除的思路，向下调整。
堆删除的思路对堆排序来说很重要，关键在于首元素和尾元素的交换。
堆排序关键思路：当我们想让数组从小到大排序，则建立大堆；从大到小排序，则建立小堆。当我们通过大堆找到最大值后，将其与尾元素交换，然后size--达到伪删除的目的（顺序表的删除也可视为一种伪删除，即数据没有被销毁，只是访问不到），重复建堆并交换，次大的数据在最大的数据之前，以此类推......
堆排序的实现注意事项：我们实现堆排序的时候，不要像实现堆那样开辟一整块空间，再push数据、建堆等操作。我们直接在数组上建堆，因为堆排序的物理结构归根到底还是顺序表，只要熟悉堆的操作，我们直接通过下标进行访问修改即可。
Topk问题：这类问题的关键就是要建立k个元素的堆，从小到大排序，则建立大堆；从大到小排序，则建立小堆，从第k + 1个数开始每次删去堆顶元素，再push一个数至堆顶，再向下调整。满足条件的数沉入堆底，不会被删除。理解了这里，那么Topk问题就迎刃而解了。
4.堆和堆排序实现代码：
Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}Heap;
void HeapInit(Heap* p);
void HeapDesTroy(Heap* p);
void HPDataTypeSwap(HPDataType* x1, HPDataType* x2);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int size, int parent);
void HeapPush(Heap* p, HPDataType x);
void HeapPop(Heap* p);
bool HeapEmpty(Heap* p);
int HeapSize(Heap* p);
HPDataType HeapTop(Heap* p);
void HeapSort(HPDataType* arr, int size);Heap.c
#pragma once
#include "Heap.h"
void HeapInit(Heap* p)
{
assert(p);
p->capacity = p->size = 0;
p->arr = NULL;
}
void HeapDesTroy(Heap* p)
{
assert(p);
free(p->arr);
p->arr = NULL;
p->capacity = p->size = 0;
}
void HPDataTypeSwap(HPDataType* x1, HPDataType* x2)
{
assert(x1 && x2);
HPDataType tmp = *x1;
*x1 = *x2;
*x2 = tmp;
}
void AdjustUp(HPDataType* arr, int child)
{
assert(arr);
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[child] < arr[parent])
{
HPDataTypeSwap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(HPDataType* arr, int size, int parent)
{
assert(arr);
int child = parent * 2 + 1;
if (parent * 2 + 2 < size)
{
child = arr[child] < arr[child + 1] ? child : child + 1;
}
while (child < size)
{
if (arr[child] < arr[parent])
{
HPDataTypeSwap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
if (parent * 2 + 2 < size)
{
child = arr[child] < arr[child + 1] ? child : child + 1;
}
}
else
{
break;
}
}
}
void HeapPush(Heap* p, HPDataType x)
{
assert(p);
if (p->capacity == p->size)
{
p->capacity = p->capacity == 0 ? 4 : 2 * p->capacity;
HPDataType* tmp = (HPDataType*)realloc(p->arr, sizeof(HPDataType) * p->capacity);
assert(tmp);
p->arr = tmp;
}
p->arr[p->size++] = x;
AdjustUp(p->arr, p->size - 1);
}
void HeapPop(Heap* p)
{
assert(p);
HPDataTypeSwap(&p->arr[0], &p->arr[p->size - 1]);
p->size--;
AdjustDown(p->arr, p->size, 0);
}
bool HeapEmpty(Heap* p)
{
assert(p);
return p->size == 0;
}
int HeapSize(Heap* p)
{
assert(p);
return p->size;
}
HPDataType HeapTop(Heap* p)
{
assert(p);
if (p->size == 0)
{
printf("空堆，无数据\n");
assert(p->size != 0);
}
return p->arr[0];
}
void HeapSort(HPDataType* arr, int size)
{
assert(arr);
int parent = (size - 2) / 2;
while (parent >= 0)
{
AdjustDown(arr, size, parent);
parent--;
}
int sz = size;
while (--size)
{
HPDataTypeSwap(&arr[0], &arr[size]);
AdjustDown(arr, size, 0);
}
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}堆测试代码：
#include "Heap.h"
//小堆的相关功能实现
int main()
{
Heap p;
HeapInit(&p);
HPDataType arr[] = { 10, 9, 8, 7, 4, 5, 6, 2, 1, 3, 12, 11, 13, 15, 14, 16, 19, 17, 18, 20 };
for (int i = 0; i < sizeof(arr) / sizeof(HPDataType); i++)
{
HeapPush(&p, arr[i]);
}
while (HeapEmpty(&p) != true)
{
printf("%d ", HeapTop(&p));
HeapPop(&p);
}
HeapDesTroy(&p);
return 0;
}
堆排序测试代码：
#include "Heap.h"
//从大到小
int main()
{
HPDataType arr[] = { 10, 9, 8, 7, 4, 5, 6, 2, 1, 3, 12, 11, 13, 15, 14, 16, 19, 17, 18, 20 };
HeapSort(arr, sizeof(arr) / sizeof(HPDataType));
return 0;
}
