数据结构——lesson7二叉树 堆的介绍与实现
一、 堆的概念及结构
如果有一个关键码的集合K = { k1，k2 ，k3 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki <=k(2i+1 )且 ki<=k(2i+2) ( ki >=k(2i+1 )且 ki>=k(2i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
??简单来说大堆指的是父节点都大于子节点的完全二叉树； 小堆指的是父节点都小于子节点的完全二叉树； 大堆的根节点是最大的，小堆是最小的。
二、堆的实现
1.堆的创建
我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
下面是堆创建以及实现堆所需的函数，后文将一一介绍
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
//构建一个结构体封装堆
typedef struct Heap
{
HPDataType* a;//数组顺序表
int size;//堆元素个数
int capacity;//数组空间
}Heap;
//以下是实现堆的函数
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);2.堆的初始化
void HeapInit(Heap* hp)
//堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}3.堆的删除（删除堆顶元素）
void HeapPop(Heap* hp)
在介绍堆的删除之前我们先介绍堆向下调整算法； 显而易见堆的删除不可能像顺序表那样删除尾部元素size–就行，我们需要玩点高深的，删除顶部元素，但删除顶部元素就没办法保证它删除后还是一个堆了，这就要利用我们下面介绍的向下调整算法。
int a[] = {1,8,3,5,7,6}; 该数组逻辑结构可以看成一个完全二叉树如下图所示：
我们可以从图中看出它是一颗完全二叉树,但并不是所有的父节点都大于或小于其子节点，所以不是一个堆，接下来我们就可以通过下面介绍的堆向下调整算法将它调整为一个堆。
堆向下调整算法 现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
?? ①下面介绍第一种向下调整为小堆； 前提条件——左右子树都是小堆
//堆向下调整算法（小堆）
void AdjustDown(HPDataType* a, int n,int parent)
{
int child = parent * 2 + 1;
//向下调整
while (parent < n)
{
//找到较小的孩子节点
if (child + 1 < n && a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
}
else
break;
}
}因为要调整为小堆，所以要找到孩子中较小的一个进行比较； 如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。 调整前：
调整后：
??Swap函数在这里
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}??②第二种向下调整为大堆；前提条件——左右子树都是大堆
//堆向下调整算法（大堆）
void AdjustDown(HPDataType* a, int n,int parent)
{
int child = parent * 2 + 1;
//向下调整
while (child < n)
{
//找到较大的孩子节点
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
}
else
break;
}
}因为要调整为大堆，所以要找到孩子中较大的一个进行比较； 如果父节点大于于较大的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是大堆。
??我们这里使用小堆向下调整，大家可以根据自己的需求选择哦~
学习完堆向下调整我们知道只要左右子树是一个堆，那么我们就可以从根节点开始向下调整直到整个二叉树成为一个堆；?? 所以删除堆顶元素我们就可以将堆顶元素与最后一个元素交换一下位置，这样除了根节点，其余父子关系都没变，左右子树还是堆，删除交换后的最后一个元素（也就是原来的根节点）；?? 我们再利用堆向下调整算法，将整个二叉树再次复原为堆。??
堆顶元素删除
// 堆的删除，删除堆顶元素
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));//判空函数将在后文介绍
//交换首尾元素
Swap(&hp->a[0], &hp->a[hp->size - 1]);
//size要记得--,表示删除元素
hp->size--;
//向下调整算法
AdjustDown(hp->a, hp->size, 0);
}4.堆的插入
void HeapPush(Heap* hp, HPDataType x)
我们知道堆的父节点必须都大于或小于子节点，那么往一个堆中插入元素是没办法保证大于或小于其父节点的，所以我们插入之后需要调整这个二叉树来保证堆； 这里就要用到堆向上调整算法了；注意下面是小堆的调整
堆向上调整算法
//向上调整
void AdjustUp(HPDataType* a,int child)
{
//找到双亲节点
int parent = (child - 1) / 2;
//向上调整
while (child > 0)
{
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}堆向上调整类似于向下调整也有大堆小堆之分，大家可以依照堆的向下调整自己试试看写一下大堆的向上调整
堆的插入
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//判断容量
if (hp->size == hp->capacity)//容量满了扩容
{
int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
if (new == NULL)
{
perror("realloc fail");
return;
}
hp->a = new;
hp->capacity = newcapacity;
}
//尾插
hp->a[hp->size] = x;
hp->size++;
//向上调整算法
AdjustUp(hp->a,hp->size-1);
}这里要注意插入数据要判断容量，如果满了要用realloc函数扩容，对于realloc函数有疑问的可以看土土的动态内存函数博客??——c语言动态内存函数介绍； 如果第一次扩容，就将空间扩为4个HPDataType，其余扩原来的两倍
5. 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));//判空
return hp->a[0];//顶即下标为0的元素
}6. 堆的数据个数
int HeapSize(Heap* hp)
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}堆的数据个数即为结构体中的size，直接返回即可
7.堆的销毁
void HeapDestory(Heap* hp)
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}，在内存中用realloc函数开辟空间用 free释放即可
??判空函数在这里~ int HeapEmpty(Heap* hp)
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}8.堆实现代码如下
#include"Heap.h"
//堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//堆向下调整算法
void AdjustDown(HPDataType* a, int n,int parent)
{
//找到较小的孩子节点
int child = parent * 2 + 1;
//向下调整
while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
}
else
break;
}
}
//向上调整
void AdjustUp(HPDataType* a,int child)
{
//找到双亲节点
int parent = (child - 1) / 2;
//向上调整
while (child > 0)
{
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//判断容量
if (hp->size == hp->capacity)//容量满了扩容
{
int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
if (new == NULL)
{
perror("realloc fail");
return;
}
hp->a = new;
hp->capacity = newcapacity;
}
//尾插
hp->a[hp->size] = x;
hp->size++;
//向上调整算法
AdjustUp(hp->a,hp->size-1);
}
// 堆的删除，删除堆顶元素
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
//向下调整算法
AdjustDown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}测试代码如下：
#include"Heap.h"
int main()
{
Heap hp;
HeapInit(&hp);
int a[] = { 65,100,70,32,50,60 };
for (int i = 0; i < 6; i++)
{
HeapPush(&hp, a[i]);
}
while (!HeapEmpty(&hp))
{
int top = HeapTop(&hp);
printf("%d\n", top);
HeapPop(&hp);
}
return 0;
}运行结果如下：
居然是升序诶~大家知道原因吗?? 可以根据上面的代码和介绍理解为自己解答哦~土土将在下一篇博客介绍堆的应用，会详细介绍堆排序哦 ~??
三、结语
以上就是堆的介绍和实现啦~??需要注意的是堆有大堆小堆之分，相应的函数也就有两种，这里简单介绍了小堆的实现，大堆介绍了一点，大家可以通过上面介绍的自己探索大堆的实现，此外堆向上调整与向下调整是一个重难点大家要多花时间去理解与记忆哦 ~完结撒花 ~????