数据结构——二叉树的顺序结构及实现（堆）_二叉树顺序存储

前言

此文章主要讲解二叉树的顺序结构，堆的实现。在阅读本文之前，希望大家可以对二叉树进行一定程度了解。

数据结构——树与二叉树_Massachusetts_11的博客-CSDN博客

目录

前言

1. 二叉树的顺序结构

2.堆的概念及结构

转换原理

3. 堆的实现

3.1初始化

3.2销毁

3.2打印

3.3尾插

向上调整算法

3.4头删

向下调整算法

3.5剩余 

4.堆——总代码

4.1 头文件：Heap.h

4.2源文件：Heap.c

4.3测试文件：test.c

4.4测试结果

5. 堆的应用

5.1堆排序

5.1.1基础版本

5.1.2升级版

5.2TopK问题

题目：

分析：

 实现：

---

1. 二叉树的顺序结构

2.堆的概念及结构

以上是堆的定义，看不懂不重要，我们接下来慢慢解释：

1.首先堆必须时一棵完全二叉树

2.堆一般分为两种：

• 小根堆：任意一个节点的两个子节点都比自己的值大或相等，也就是根最小，整个二叉树从上到下递增。

• 大根堆： 任意一个节点的两个子节点都比自己的值小或相等，也就是根最大，整个二叉树从上到下递减。

转换原理：

那么问题来了，这里的存储结构是如何向逻辑结构去实现的呢？

不知大家是否还记得树与二叉树一文中二叉树性质的这几条

也就是说：对于任意一个节点，我们设它的下标为i，则它的左孩子节点下标就是2*i +1 ，右孩子就是2*i + 2，父节点下标就是（i - 1) / 2。

（可能大家也发现了，这里的父节点如果用两个子节点去倒推应该有两个不同的结果，但我们所求的下标必须是一个整型，由于c语言向零取整的原则，两个表达式可合成一个  （i - 1) / 2    ）

我们不妨来验证一下：

 这里元素28的下标是4，它的父节点下标计算后是（4-1）/ 2 = 1，恰好是18元素

它的左子节点2*4+1 = 9，恰好是37元素，它的右子节点2*4+2 = 10，恰好是10元素。

有了以上这些基础，我们也可以进行一下堆的实现了。

3. 堆的实现

与顺序表相同，我们同样也实现一下堆的增删查改

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestroy(HP* php);
//打印堆
void HeapPrint(HP* php);
//尾插元素
void HeapPush(HP* php, HPDataType x);
//头删元素
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//计算节点个数
size_t HeapSize(HP* php);
//返回堆头节点
HPDataType HeapTop(HP* php);

3.1初始化

既然要实现，我们就需要从物理存储角度去思考。

与动态顺序表相同，我们为堆设置一个数组，同时为它附加两个记录：元素个数和容量大小（方便扩容）

在没有元素之前，数组置空，元素个数和容量都为0，后续在尾插元素时，再对堆进行判断，进行扩容

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

3.2销毁

对静态开辟的数组进行释放；

元素个数和容量都置零；

void HeapDestroy(HP* php)
{
	assert(php);
	assert(php->a);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

3.2打印

可以选择打印出二叉树的外形，但太复杂了