【数据结构】 二叉树的顺序结构——堆的实现

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储 。

一、堆的概念及结构

父节点比孩子结点大 是大堆

父节点比孩子结点小 是小堆

堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值

堆总是一棵完全二叉树。

二、堆的实现

接口函数

//Heap.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

函数实现

//Heap.c
#include"Heap.h"
// 小堆
// 堆的构建
void HeapCreate(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_size = 0;
	hp-> _capacity = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_size = 0;
	hp->_capacity = 0;
}
void swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void AdjustUp(Heap* hp, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->_a[child] < hp->_a[parent])
		{
			swap(&hp->_a[child], &hp->_a[parent]);
			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 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	//向上调整
	AdjustUp(hp,hp->_size-1);
}
void AdjustDown(Heap* hp)
{
	int parent = 0;
	int child = 2 * parent + 1;
	while (child <= hp->_size-1)
	{
		//假设法 左孩子是较小的孩子 如果不是 更新一下
		if (hp->_a[child] > hp->_a[child + 1])
		{
			child++;
		}
		//比较 较小孩子与父节点大小 如果 较小孩子比父节点小 则交换
		if (hp->_a[child] < hp->_a[parent])
		{
			//较小孩子 与 父节点交换
			swap(&hp->_a[parent], &hp->_a[child]);
		}
		else
		{
			break;
		}
		//更新父节点、孩子节点 下标
		parent = child;
		child = 2 * parent + 1;
	}
}
// 堆的删除 （删除的是堆顶 -> 找 次大or次小）
//堆顶数据先与最后一个结点交换 交换到堆顶的数据 向下调整
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	//堆顶数据与最后一个数据 交换
	swap(&hp->_a[0],&hp->_a[hp->_size - 1]);
	//删除此时的最后一个数据（堆顶）
	hp->_size--;
	//将 新的堆顶向下调整 
	AdjustDown(hp);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

测试函数功能

//test.c
#include"Heap.h"
int main()
{
	Heap hp;
	HeapCreate(&hp);
	HPDataType a[] = { 2, 4, 9, 1, 12, 0, 5, 3, 7 };
	for (int i = 0; i < sizeof(a) / sizeof(HPDataType); i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	HeapDestory(&hp);
	return 0;
}