堆的概念
堆是完全二叉树，分为大堆和小堆。大堆：任何一个父亲都大于等于孩子，小堆：任何一个父亲都小于等于孩子。
堆的实现
目录
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆的初始化和销毁
void HPInit(HP* php);
void HPDestroy(HP* php);
//堆的插入和删除
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆数据和判空
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);
//向上调整和向下调整
void AdJustUp(HPDataType* a, int child);
void AdJustDown(HPDataType* a, int n, int parent);1.堆的初始化
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}可以选择在堆的初始化过程直接对空间大小进行赋值，在这里选择不开空间。
2.堆的销毁
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}3.交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}4.向上调整
堆在数组中存储，所以根节点的小标为孩子节点下标减一再除以二，向上调整即将孩子节点向上调整，直到满足要求的大堆(小堆)建成。
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;
}
}
}5.向下调整
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;
}
else
{
break;
}
}
}6.堆的插入
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 fail!");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdJustUp(php->a, php->size - 1);
}我们选择在堆插入函数中进行空间的开创。
7.堆数据删除
对于堆中数据的删除，删除叶子结点数据意义不大，我们主要是要删除顶层节点数据，思路将顶部数据进行调整到最后的叶子结点处，在对其进行删除即可。
void HPPop(HP* php)//向下调整算法,可用于topk问题（找最大(最小)的几个值）
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdJustDown(php->a, php->size, 0);
}8.取堆顶数据
对于只有一条语句的函数，我们为了方便调控，仍进行函数调用。
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}9.堆的判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}堆排序
建堆
通过循环调用向上调整函数，可以将数组调整为堆。代码如下：
void HeapSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
AdJustUp(a, i);
}
}另外，若使用向下调整建堆时间复杂度会更低
排序
升序建大堆
如果升序建小堆，将顶层最小数据取出后，导致后面数据顺序全部混乱，所以我们建大堆。
将最大的数往堆最后位置数据交换，再将其放入新数组的最后一位即可。代码如下：
void HeapSort(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, end, 0);
--end;
}
}
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;
}
else
{
break;
}
}
//向上调整同理
}降序建小堆
如果降序建大堆，将顶层最大数据取出后，导致后面数据顺序全部混乱，所以我们建小堆。
将最小的数往堆最后位置数据交换，再将其放入新数组的最后一位即可。代码如下：
void HeapSort(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, end, 0);
--end;
}
}
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;
}
else
{
break;
}
}
//向上调整同理
}如果觉得我写得不错的话，请别忘了点赞收藏加评论！！
