数据结构堆排序中堆的建立、调整、插入、删除等操作的详解（题目讲解简单易懂）

水深无声 2023-10-09 20:08 31阅读 0赞

## 堆的定义 ##

首先我们要明确堆是个什么东西，简而言之堆就是一个具有特殊性质的完全二叉树

完全二叉树：一棵深度为k的有n个结点的[二叉树][Link 1]，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与[满二叉树][Link 2]中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

堆的特殊性质体现在结点与子结点的大小关系上，当父结点的值大于等于其子节点的值时候就是大根堆，反之就是小根堆

## 堆的操作 ##

在堆的[数据结构][Link 3]中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的[递归][Link 4]运算

下面我们主要以题目手工建堆以及进行插入删除等操作进行调整，这也是历年408常考的题型之一

## 堆的插入 ##

插入操作比较简单，把插入关键字插入到堆的空叶子结点中，然后依据大根堆或者小根堆的性质进行结点之间的调整即可

题目：已知关键字序列5，8，12，19，28，20，15，22为小根堆，插入关键字3，调整好之后得到的小根堆是？

这种题目我们先画出原本的小根堆，注意这里结点序号的对应为父结点为i，则左孩子为2i，右孩子为2i+1

![9050380a08dd4e9c97ad5c0a86f2a87d.jpeg][]

## 堆的删除 ##

堆的删除稍微复杂一些，堆删除一般指取根结点，这样实际上删除了序列中的最大值/最小值，**这时我们用堆中最后一个元素插入根结点**，然后再依据大根堆或者小根堆的性质调整即可

题目：对关键字序列23，17，72，60，25，8，68，71，52进行最小堆排序，输出两个最小关键字之后的剩余堆是？

先建立堆，然后每次输出/删除之后用最后一个结点补上再调整即可

![b11814c06bff4469956aec7930096a82.png][]

## 空堆建立 ##

下面我们就以2021年408中真题进行讲解

题目：将关键字6，9，1，5，8，4，7依次插入到初始为空的大根堆H中，得到的H是什么？

做题方法：按上面插入的方法，依次插入到叶子结点，有不符合性质的马上调整即可

![1fed4942307c40a1a86e69a9fc370802.png][]

## 堆的调整 ##

有了上面的基础之后，堆的调整就十分好理解，堆的调整是指一个原本的堆经过调整之后形成大根堆或者小根堆，注意根上面空堆的插入建立区别开

题目：将序列6，1，5，9，8，4，7建成大根堆时，正确的序列变化过程为？

解题方法：先写出初始堆，这时一般它是不满足大根堆或者小根堆的性质，**然后从序列末尾进行调整即可，调整完一轮后再往下看有没有需要调整的，直到符合大根堆或者小根堆的性质即可**

![39652b1fec5041fa8f80420d80f3df33.png][]

**创作不易 觉得有帮助请点赞关注收藏~~~**

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879
[Link 2]: https://baike.baidu.com/item/%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91/7773283
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
[Link 4]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[9050380a08dd4e9c97ad5c0a86f2a87d.jpeg]: https://img-blog.csdnimg.cn/9050380a08dd4e9c97ad5c0a86f2a87d.jpeg
[b11814c06bff4469956aec7930096a82.png]: https://img-blog.csdnimg.cn/b11814c06bff4469956aec7930096a82.png
[1fed4942307c40a1a86e69a9fc370802.png]: https://img-blog.csdnimg.cn/1fed4942307c40a1a86e69a9fc370802.png
[39652b1fec5041fa8f80420d80f3df33.png]: https://img-blog.csdnimg.cn/39652b1fec5041fa8f80420d80f3df33.png