【玩转二叉树②】堆的C语言实现（动图演绎）_C

学习导航

- - 一、堆的基本介绍
  - 二、堆的C语言实现
  - - ①堆的结构体定义
    - ②堆的初始化
    - ③堆的销毁
    - ④堆元素的插入
    - ⑤堆元素的删除
  - 三、初步实现堆排序

一、堆的基本介绍

①基本概念:
所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。

也就是说在物理结构上是以数组的形式存储，而在逻辑结构上是以二叉树的方式使用

②分类：

父节点的元素值都小于子节点元素值 → 小根堆
父结点的元素值都大于子节点元素值 → 大根堆

③性质：
堆是一种完全二叉树，具有完全二叉树的性质

二、堆的C语言实现 ①堆的结构体定义

②堆的初始化

③堆的销毁

④堆元素的插入

1.如何插入？
【答】我们首先将新来的元素插入到数组的末尾。

但是这只是物理结构上的插入，我们还要再逻辑结构上保证它是一个堆。

即父节点都大于（或者小于）子字节的逻辑条件。

因此插入元素之后我们还需要一个 “上浮” *** 作。

来看看用代码实现上述过程（我们来实现大根堆，小根堆变个符号即可）：

2.插入函数的实现：

3.上浮过程图解：

【关键点分析】
与父节点比较交换来维持堆的逻辑结构

4.上浮函数实现：

【关键点剖析】

父节点与孩子结点的下标关系详情参见前一篇博客树的基本知识和重要性质
上浮停止有两种情况：
①孩子结点小于父节点，此时满足堆的逻辑结构，break;
②一直交换到根节点，表现为child == 0

5.上浮 *** 作时间复杂符分析：
最坏的情况是从底上浮到根节点，交换的次数就是树的深度即O(logn)

⑤堆元素的删除

1.如何删除？
【答】可以直接把数组往前移一位来覆盖堆顶的元素吗？不可以!
且不说它O(n)的时间复杂度，虽然从物理结构上讲堆顶的元素删除了，但是却破坏了堆的逻辑结构，父节点与子节点的下标关系被破坏。

正确的做法是将数组末尾的元素与堆顶的元素进行交换，这样只要对堆顶的一个元素进行“下沉” *** 作即可在删除堆顶元素的基础上又不破坏逻辑结构

2.删除函数的实现：

3.下沉过程图解：

【关键点分析】

将数组末尾元素和堆顶的元素进行交换
对堆顶的元素进行“下沉” *** 作

4.下沉函数实现：

【关键点剖析】

因为要创建大根堆，所以在父节点需要与左右孩子结点的较大值进行比较。

当然右孩子有可能不存在，所以首先要进行范围判断
下沉停止的两种情况：
①：父节点比两个子节点都大，则符合堆的逻辑结构，交换停止
②child结点超出数组范围，说明没有孩子结点了。

交换停止

5.下沉复杂度分析
同上分析，算法的时间复杂度为O(logn)