【数据结构】堆（超详细）

前言

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。在现实中我们通常把堆 (一种完全二叉树) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念及结构

【大根堆和小根堆】：

根结点最大的堆叫做大根堆，树中所有父亲都大于或等于孩子。

根结点最小的堆叫做小根堆，树中所有父亲都小于或等于孩子。

堆的实现

首先新建一个工程：

Heap.h（堆的类型定义、接口函数声明、引用的头文件）
Heap.c（堆接口函数的实现）
test.c（主函数、测试栈各个接口功能）

完整的代码放在后面（包括测试代码），这里就不会展示测试的效果图。大家可以自己别敲边按测试代码测试。图解会写的很详细的，么么😙

堆的向下调整算法（建小堆为例）

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int arr[] = {27,15,19,18,28,34,65,49,25,37};

思想：
1.选出左右孩子较小的一个值，
2.然后和父亲进行比较，如果比父亲小就进行交换，并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。如果比父亲大，则停止向下调整，此时该树就成小堆。

//交换函数
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}//向下调整算法
void AdjustDown(HDataType* a, int size, int parent)
{//假设左孩子小int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child])//确保有右孩子，如果右孩子小，更新到右边{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//更新父亲孩子下标，parent = child;child = child * 2 + 1;}else // 如果父亲小于孩子，说明已经为小堆了，停止调整{break;}}}

堆的向上调整算法（建小堆为例）

当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法。
假设在这个堆int arr[] = {15,18,19,25,28,34,65,49,27,37}的末尾插入16.

思想：
1.将要插入孩子的值与父亲的值比较。
2.若插入孩子的值比父亲的值小，则交换插入孩子的值与父亲的值，并将父亲的位置当作新的插入孩子的值继续进行向上调整。若插入孩子的值比父亲的值大，则停止向上调整，此时该树就成小堆。

//交换函数
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}//向上调整算法
void AdjustUp(HDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

堆的初始化

//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

销毁堆

//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的插入

数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

//堆的插入
void HPPush(HP* php, HDataType x)
{assert(php);//检查空间是否足够插入，不够则扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * newcapacity);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);// 从插入的元素开始，进行向上调整，保持它依然是堆
}

堆的删除(规定删堆顶的数据)

堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，
1.将堆顶的数据与最后一个结点的数据交换，
2.删除堆种最后一个元素，此时左子树和右子树还是小堆
3.再对堆进行向下调整

//堆的删除(规定删堆顶的数据)
void HPPop(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);// 从根节点开始，对剩下元素进行向下调整成大堆，保持它依然是堆
}

取堆顶元素

//取堆顶元素
HDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);//确保堆里有数据return php->a[0];//返回堆顶数据
}

判断堆是否为空

//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;//判断堆中数据是否为0
}

获取堆的个数

//获取堆的个数
int HPSize(HP* php)
{assert(php);return php->size;//返回堆中数据个数
}

完整代码（包括测试代码）

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef  int HDataType;
typedef struct Heap
{HDataType* a;int size;int capacity;}HP;//交换函数
void Swap(HDataType* p1, HDataType* p2);
//向上调整算法
void AdjustUp(HDataType* a, int child);
//向下调整算法
void AdjustDown(HDataType* a, int size, int parent);//初始化堆
void HPInit(HP* php);
//销毁堆
void PHDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HDataType x);
//堆的删除(规定删堆顶的数据)
void HPPop(HP* php);
//取堆顶元素
HDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//获取堆的个数
int HPSize(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//小堆
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}//向下调整算法
void AdjustDown(HDataType* a, int size, int parent)
{//假设左孩子小int child = parent * 2 + 1;while (child < size){	if (child + 1 < size && a[child + 1] < a[child])//确保有右孩子，如果错了，更新到右边{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}}
//向上调整算法
void AdjustUp(HDataType* a, int child)//可以用递归写，没必要，用循环就可以
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}}
//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;}//堆的插入
void HPPush(HP* php, HDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * newcapacity);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);
}//堆的删除(规定删堆顶的数据)
void HPPop(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);
}//取堆顶元素
HDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//获取堆的个数
int HPSize(HP* php)
{assert(php);return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"int main()
{int a[] = { 4,3,7,9,1,5,8,2,8 };int sz = sizeof(a) / sizeof(a[0]);HP hp;HPInit(&hp);for (int i = 0; i < sz; i++){HPPush(&hp, a[i]);}//int k = 5;//while (k--)//{//	printf("%d\n", HPTop(&hp));//	HPPop(&hp);//}while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");return 0;
}