二叉堆例程

二叉堆例程

二叉堆是一种优先队列的数据结构，具有2种性质：结构性质和堆序性。这里讨论都基于最小二叉堆，这种二叉堆对最小元素的访问非常高效。

二叉堆的ADT操作主要包括Insert（插入）和DeleteMin（删除最小元）。

1、结构性质：堆是一棵完全二叉树（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 都被填满，第 h 层所有的结点都连续集中在最左边），如下图。

（1）因为完全二叉树很有规律，因此可以用一个数组而不需要用指针存储，可以存储成如下形式，其中[0]地址处元素常常用于标记（对于最小二叉堆而言，存储一个非常小的值），这只是为了编程方便，当然也可以不用该标记。

（2）对于数组中任一位置i处的元素，其左儿子在位置2*i上，右儿子在2*i+1上。这条信息很有用，也正因为这样，我们可以很方便的不用指针而只用数组就能访问左右儿子。

2、堆序性：

由于我们想快速的找到最小元，因此最小元应在根上。我们可以以O(1)时间找到最小值。

堆序性指，在一个堆中，每一个节点X，X父亲中的关键字小于（或等于）X中的关键字，根节点除外（因为没有父亲）。

3、插入

为将一个元素 X 插入到堆中，我们在下一个可用位置创建一个空穴，否则该堆将不是完全数。如果 X 可以放在该空穴中而不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上冒一步。继续改过程直到 X 能被放入空穴中为止。

这样一般的策略叫做上滤( percolate up )；新元素在堆中上滤直到找出正确的位置。