目录

堆的概念 

堆的结构

实现堆

初始化堆

释放堆

插入数据（默认小堆插入）

向上调整算法

判断堆是否为空

获取堆元素总个数

删除数据（默认删除堆顶数据）

向下调整算法 

访问堆顶元素

Heap.h 的所有代码

Heap.c 的所有代码  

---

堆的概念 

堆的条件：

• 堆是一颗完全二叉树
• 大堆：树中任何一个父亲都大于或等于孩子
• 小堆：树中任何一个父亲都小于或等于孩子

大堆/小堆示意图：

• 堆中某个节点的值总是不大于或不小于其父节点的值
• 堆总是一颗完全二叉树

堆的物理结构和逻辑结构：

• 堆的物理结构是一个顺序表，也就是数组存储
• 堆的逻辑结构是一个完全二叉树

---

堆的结构

// 数据类型
typedef int HPDataType;

// 堆结构
typedef struct Heap
{
	HPDataType* a; //指向存储堆数据的指针

	int size; //有效数据个数

	int capacity; //容量
}HP;

堆的物理结构就是顺序表，所以定义一个顺序表的结构创建堆

---

实现堆

初始化堆

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

---

释放堆

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->capacity = 0;
	php->size = 0;
}

---

插入数据（默认小堆插入）

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	// 插入数据前，先判断是否需要扩容
	if (php->capacity == php->size)
	{
		// 2倍扩容
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);

		// 判断是否扩容成功
		if (tmp == NULL)
		{
			perror("reallo fail");
			return;
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	// 插入数据
	php->a[php->size] = x;
	php->size++;

	// 向上调整
	AdjustDwon(php->a, php->size - 1);
}

插入前先判断是否需要扩容，需要扩容则扩容
因为堆的物理结构是顺序表，所以先在顺序表尾部插入数据
再通过向上调整算法保证插入数据后还是堆

向上调整算法

static void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			// 交换
			HPDataType tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			// 迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

插入数据后，要保持堆结构，那么就需要向上调整
向上调整只需要调整插入数据的父亲节点或者父亲的父亲节点，直到根节点，其他的节点不会影响堆的改变
以小堆为例，任何一个父亲节点都要小于等于孩子节点，那么插入的数据就当作孩子节点，只要父亲节点大于孩子节点就交换，直到交换到根节点或者不大于就跳出交换
这样就能完成对小堆的插入数据

测试代码：

           32

        /         \

    50           60

   /   \          /

100 65    70

---

判断堆是否为空

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

---

获取堆元素总个数

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

---

删除数据（默认删除堆顶数据）

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	
	// 首尾元素交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	// 删除堆顶元素（也就是尾删）
	php->size--;

	// 向下调整
	AdjustDown(php->a, php->size, 0);
}

删除堆顶元素后，要保证堆的大致结构不变，所以先交换首尾元素
再删除尾元素，交换后的尾元素也就是堆顶元素
这样就能做到堆的结构大致不变，只是需要把新的堆顶元素调整到相对应的位置

向下调整算法 

static void AdjustDown(HPDataType* 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[parent] > a[child])
		{
			// 交换
			Swap(&a[parent], &a[child]);
			
			// 迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

根据 parent * 2 + 1 公式，找到父亲节点的左孩子节点
再找到左右孩子中小的那个孩子（注意：有左孩子的情况下不一定有右孩子，所以要先判断）
判断是否需要交换，需要交换则交换再迭代，不需要交换说明首尾元素交换后依然是给堆结构，直接退出循环即可

测试代码：

          32

       /      \

    50      70

   /   \ 

100 71 

---

访问堆顶元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

---

Heap.h 的所有代码

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.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 HeapPrint(HP* php);

// 删除数据（删除堆顶元素）
void HeapPop(HP* php);

// 判空
bool HeapEmpty(HP* php);

// 堆元素总个数
int HeapSize(HP* php);

// 访问堆顶元素
HPDataType HeapTop(HP* php);

---

Heap.c 的所有代码 

#include"Heap.h"

// 初始化堆
void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

// 释放堆
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->capacity = 0;
	php->size = 0;
}

// 交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 向上调整
static 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;
		}
	}
}

// 插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	// 插入数据前，先判断是否需要扩容
	if (php->capacity == php->size)
	{
		// 2倍扩容
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);

		// 判断是否扩容成功
		if (tmp == NULL)
		{
			perror("reallo fail");
			return;
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	// 插入数据
	php->a[php->size] = x;
	php->size++;

	// 向上调整
	AdjustUp(php->a, php->size - 1);
}

// 打印
void HeapPrint(HP* php)
{
	assert(php);

	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

// 向下调整
static void AdjustDown(HPDataType* 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[parent] > a[child])
		{
			// 交换
			Swap(&a[parent], &a[child]);
			
			// 迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 删除数据（删除堆顶元素）
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	
	// 首尾元素交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	// 删除堆顶元素（也就是尾删）
	php->size--;

	// 向下调整
	AdjustDown(php->a, php->size, 0);
}

// 判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

// 堆元素总个数
int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

// 访问堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}