堆 (heap) 是具有这样性质的数据结构:
- 完全二叉树
- 所有节点的值大于等于(或小于等于)子节点的值
堆 (heap) 又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。在队列中,我们可以进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中,我们不是按照元素进入队列的先后顺序取出元素的,而是按照元素的优先级取出元素。
这就好像候机的时候,无论谁先到达候机厅,总是头等舱的乘客先登机,然后是商务舱的乘客,最后是经济舱的乘客。每个乘客都有头等舱、商务舱、经济舱三种个键值(key)中的一个。头等舱->商务舱->经济舱依次享有从高到低的优先级。
再比如,封建社会的等级制度,也是一个堆。在这个堆中,国王、贵族、骑士和农民是从高到低的优先级。
堆属性
堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。
在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。
这是一个最大堆,,因为每一个父节点的值都比其子节点要大。10
比 7
和 2
都大。7
比 5
和 1
都大。
根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常的有用,因为堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。
注意:堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。
堆的应用:
- 构建优先队列
- 堆排序
- 快速找出一个集合中的最小值(或者最大值)
堆节点的访问
通常堆是通过一维数组来实现。当数组起始位置为 0 时,i
是节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:
// 子节点 i 的父节点位置
parent(i) = floor((i - 1)/2)
// 父节点i的左子节点在位置
left(i) = 2i + 1
// 父节点i的右子节点在位置
right(i) = 2i + 2
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。