算法 之 堆 - 简介

在许多算法中，需要支持下面两种元素运算的数据结构：插入元素和寻找最大值元素。支持这两种运算的数据结构称为优先队列。

如果使用普通队列，那么寻找最大元素需要搜索整个队列，开销比较大；如果采用排序数组，那么插入运算就需要移动很多元素，开销也会比较大。优先队列的有效实现是使用一种称为堆的简单数据结构。

 

一个（二叉）堆是一个几乎完全的二叉树，它的每个节点都满足堆的特性：如果v和p(v)分别是节点和它的父节点，那么存储在p(v)中的数据键值不小于存储在v中数据项的键值。

 

这样，堆的特性蕴含着：沿着每条从根到叶子的路径，元素的键值以非升序排列。

有n个节点的堆T（一个几乎完全的二叉树），可以由一个数组H[1...n]用下面的方式来表示：

    · T的根节点存储在H[1]中。

    · 假设T的节点x存储在H[j]中，如果它有左子节点，这个子节点存储在H[2j]中；如果他也有右子节点，这个子节点存储在H[2j+1]中。

    · 元素H[j]的父节点如果不是根节点，则存储在H[⌊j/2⌋]中。

 

如果堆中的节点有右子节点，则它一定也有左子节点，这是从几乎完全的二叉树的定义的来的。因此堆可以看作是二叉树，而它实质上是一个数组H[1...n]。它有如下性质：对于任何索引j，2 ≤ j ≤ n，key(H[⌊j/2⌋]) ≥ key (H[j])。

 

下图是一个分别用树和数组来表示的堆得例子。为了简化这张图，我们把存储在堆中的数据项的键看作是数据项本身。在图中我们注意到，如果树的节点以自顶向下、从左到右的方法，按1到n的顺序编号，那么每一项H[i]在对应的树中表示成为编号为i的节点。在图中，这个编号由树节点旁的标号指明。这样，用这种方法以数组形式给出一个堆，可以很容易构造出它的相应的树，反之亦然。

堆上的运算：

    · Sift-up

    · Sift-down

    · Insert

    · Delete

    · MakeHeap

    · HeapSort