数据结构初阶之堆的介绍与堆的实现
一、堆的概念与结构
如果有一个关键码的集合
，把它的所有元素按完全二叉树的顺序存储在一个一维数组中，并满足：
，则称为小堆（或大堆）。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆具有以下性质：
（1）堆中某个结点的值总是不大于或不小于其父结点的值；
（2）堆总是一棵完全二叉树。
二叉树的性质：
对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
（1）若 i > 0，i 位置结点的双亲序号：( i - 1 ) / 2 ；i = 0 时，i 为根结点编号，无双亲结点。
（2）若 2 * i + 1 < n，左孩子序号：2 * i + 1 。2 * i + 1 >= n 无左孩子。
（3）若 2 * i + 2 < n，右孩子序号：2 * i + 2 。2 * i + 2 >= n 无右孩子。
二、堆的实现
项目创建的时候，要创建一个头文件（.h）Heap.h ，两个源文件（.c）Heap.c ，test.c 。Heap.h 用于定义结构体和声明函数；Heap.c 用于实现函数；test.c 用于测试函数，每实现一个函数要进行相应的测试。编写代码过程中要勤测试，避免写出大量代码后再测试，如果出现问题，问题无从定位。
1、Heap.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义堆的结构
typedef int DataType;
typedef struct Heap
{
DataType* arr;
int size;
int capacity;
}Heap;
//对堆进行初始化
void Init_Heap(Heap* hp);
//判断堆是否为空
bool Empty_Heap(Heap* hp);
//销毁堆
void Destory_Heap(Heap* hp);
//打印堆
void Print_Heap(Heap* hp);
//交换数组中的两个元素
void Swap(int* x, int* y);
//向上调整算法,小堆
void Adjust_Up(DataType* arr, int child);
//入堆，往堆中增加数据
void Push_Heap(Heap* hp, DataType x);
//向下调整算法，小堆
void Adjust_Down(DataType* arr, int parent, int n);
//出堆，出的是堆顶的数据
void Pop_Heap(Heap* hp);
//取堆顶数据
DataType Get_Top_Heap(Heap* hp);
2、Heap.c
#include"Heap.h"
//对堆进行初始化
void Init_Heap(Heap* hp)
{
assert(hp);
hp->arr = NULL;
hp->capacity = hp->size = 0;
}
//判断堆是否为空
bool Empty_Heap(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
//销毁堆
void Destory_Heap(Heap* hp)
{
assert(hp);
if (hp->arr)
free(hp->arr);
hp->arr = NULL;
hp->capacity = hp->size = 0;
}
//打印堆
void Print_Heap(Heap* hp)
{
for (int i = 0; i < hp->size; i++)
{
printf("%d ", hp->arr[i]);
}
printf("\n");
}
//交换数组中的两个元素
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法，小堆
void Adjust_Up(DataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
//向下调整算法，小堆
void Adjust_Down(DataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child] > arr[child + 1])
child++;
if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//入堆，往堆中增加数据
void Push_Heap(Heap* hp, DataType x)
{
assert(hp);
if (hp->capacity == hp->size)
{
int newcapacity = (hp->size == 0) ? 4 : 2 * hp->capacity;
Heap* tmp = (Heap*)realloc(hp->arr, sizeof(newcapacity * sizeof(DataType)));
if (!tmp)
{
perror("realloc fail!");
exit(1);
}
hp->arr = tmp;
hp->capacity = newcapacity;
}
hp->arr[hp->size] = x;
Adjust_Up(hp->arr, hp->size);
hp->size++;
}
//出堆，出的是堆顶的数据
void Pop_Heap(Heap* hp)
{
assert(!Empty_Heap(hp));
Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
hp->size--;
Adjust_Down(hp->arr, 0, hp->size);
}
//取堆顶数据
DataType Get_Top_Heap(Heap* hp)
{
assert(!Empty_Heap(hp));
return hp->arr[0];
}
test.c自行测试，这里不予提供。