文章目录
- 概述
- 堆的实现
- 初始化
- 销毁
- 插入
- 删除
- 取堆顶元素
- 求堆的长度
- 判断堆是否为空
- 完整代码
概述
如果有一个关键码的集合K = {k0,k1,k2…kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <=K2*i+1 且 Ki<=K2*i+2 (Ki >= K2*i+1且 Ki>= K2*i+1) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆的实现
初始化
堆的存储结构是一个数组，堆的初始化需要定义一个数组，当前元素个数和容量。和顺序表的初始化一样。
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
销毁
释放数组a的空间，将php->capacity = php->size = 0
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
插入
堆的插入是先在数组的最后插入元素，但是需要满足堆的特点（大堆或小堆），因此需要用到向上调整算法，来实现这一特点。
介绍向上调整算法：
这里小编以实现小堆为例
在数组的最后插入一个元素child，然后这个元素与其双亲节点parent进行比较：
- 如果
child>parent：满足小堆的条件，无需交换 - 如果
child<parent：不满足小堆条件，此时需要将孩子节点child与它的双亲结点parent进行交换，此时原来的双亲结点parent变成了孩子结点child，原来的孩子节点child变成了双亲结点parent。此时，再让现在的双亲结点parent和它的双亲结点parent进行比较，如果不满足小堆，则继续交换，继续比较 - 循环结束的条件是
child>0
举个例子：
如下，在堆中插入元素10：
将10与它的双亲结点进行比较，10<28，不满足小堆的条件，将10和28，进行交换：
交换完后，此时的10变成了28的双亲结点，28变成了10的孩子结点。现在再将10与它的双亲结点比较，10<18，不满足小堆的特点，继续交换。
交换完后10变成了18的双亲结点，18变成了10的孩子结点。10和它的双亲结点比较，依然不满足小堆条件，继续交换
此时，10已经变成了根节点，并且满足小堆的条件，循环结束。
看了图解，对向上调整算法有了大概的印象，但是代码的编写，还需要再去分析一下。
定义parent是孩子的双亲结点，双亲结点parent与孩子结点child满足parent = (child - 1) / 2关系。进入循环，比较孩子节点的值和双亲结点的值，判断是否满足小堆的条件。
void swap(HPDataType* p1, HPDataType* p2)
{
int 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 = (parent - 1) / 2;
}
else
{
break;
}
}
}
写完向上调整算法，便可实现插入操作
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, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
删除
在删除操作里面，一般规定删除堆顶，即根节点
删除根节点的常规操作是将根结点和最后一个叶节点进行交换，然后尾删即可，此时根节点的左右子树依然是小堆
但是根节点不满足小队的条件，因此引入向下调整算法
向下调整算法：
和向上调整算法是一个道理
但是此时根节点是双亲结点，有两个孩子，不知道该选择哪一个孩子。这里使用到了假设法：假设左孩子小，如果假设错了，更新一下
判断双亲结点和孩子结点的大小：
- 如果双亲结点小于孩子结点，直接结束
- 如果双亲结点大于孩子结点，交换双亲结点和孩子结点的值，然后更新一下双亲结点的位置和孩子节点的位置
循环结束的条件是child<size
和向上调整算法基本一致，直接上代码:
AdjustDown(HPDataType* a,int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child] > a[child + 1] && child + 1 < size)
{
child++;
}
if (a[child] < a[parent])
{
swap(a[parent], a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
删除操作：
void HeapPop(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 HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
求堆的长度
先判断堆是否存在，直接返回堆的长度即可
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
判断堆是否为空
先判断堆是否存在，如果php->size==0，那么堆为空，返回true，反之返回false
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
完整代码
Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
// 规定删除堆顶（根节点）
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);
Heap.c
# define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
void swap(HPDataType* p1, HPDataType* p2)
{
int 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 = (parent - 1) / 2;
}
else
{
break;
}
}
}
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, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
AdjustDown(HPDataType* a,int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child] > a[child + 1] && child + 1 < size)
{
child++;
}
if (a[child] < a[parent])
{
swap(a[parent], a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(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 HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
