数据结构中，堆是如何实现排序的？

本文共计2111个文字，预计阅读时间需要9分钟。

堆（heap）是计算机科学中一种特殊的数据结构，通常被看作是一棵可视化的树形结构。堆通常是一个完全二叉树，且满足堆的性质：父节点的值总是小于或大于其子节点的值。堆分为最大堆和最小堆，其中最大堆的父节点值大于或等于子节点，最小堆则相反。堆常用于优先队列等应用场景。

堆 堆的概念

• 堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，即是一种顺序储存结构的完全二叉树。^[1]

提示：完全二叉树

• 完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树。^[2]

堆的性质

• 堆中某个结点的值总是不大于或不小于其父结点的值
• 堆总是一棵完全二叉树
• 除了根结点和最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点

最大堆最小堆

• 最大堆^[3]：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

• 最小堆^[3:1]：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。