二叉堆

  • 更新时间: 2017-09-26
  • 来源: 原创或网络
  • 浏览数: 60次
  • 字数: 9319
  • 发表评论

二叉堆是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆

父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆

1 存储

二叉堆一般用数组来表示。如果根节点在数组中的位置是1,第n个位置的子节点分别在2n和 2n+1。因此,第1个位置的子节点在2和3,第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。

如果存储数组的下标基于0,那么下标为i的节点的子节点是2i + 1与2i + 2;其父节点的下标是⌊(i − 1) ∕ 2⌋。

如下图的两个堆:

        1                        11
      /   \                      /  \
     2     3                   9     10
    /  \  /  \                / \   /  \
   4   5  6  7               5  6  7   8
  / \  / \                  /\  /\
 8  9 10 11               1  2 3  4 

将这两个堆保存在以1开始的数组中:

位置:  1  2  3  4  5  6  7  8  9 10 11
左图:  1  2  3  4  5  6  7  8  9 10 11
右图: 11  9 10  5  6  7  8  1  2  3  4

对于一个很大的堆,这种存储是低效的。因为节点的子节点很可能在另外一个内存页中。B-heap是一种效率更高的存储方式,把每个子树放到同一内存页。

如果用指针链表存储堆,那么需要能访问叶节点的方法。可以对二叉树“穿线”(threading)方式,来依序遍历这些节点。

2 基本操作

二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。

插入节点

在数组的最末尾插入新节点。然后自下而上调整子节点与父节点(称作up-heap或bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up操作):比较当前节点与父节点,不满足堆性质则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为O(log n)。

删除根节点

删除根节点用于堆排序

对于最大堆,删除根节点就是删除最大值;对于最小堆,是删除最小值。然后,把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点:对于最大堆父节点如果小于具有最大值的子节点,则交换二者。这一操作称作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至当前节点与它的子节点满足堆性质为止。

下属对最大堆的自上而下调整堆的伪代码中,数组A的下标索引值是从1开始: Max-Heapify (A, i):
left ← 2i
right ← 2i + 1
largesti
if leftheap_length[A] and A[left] > A[largest] then:
largestleft
if rightheap_length[A] and A[right] > A[largest] then:
largestright
if largesti then:
swap A[i] ↔ A[largest]
Max-Heapify(A, largest)

构造二叉堆

一个直观办法是从单节点的二叉堆开始,每次插入一个节点。其时间复杂度O(nlog⁡n)

最优算法是从一个节点元素任意放置的二叉树开始,自底向上对每一个子树执行删除根节点时的Max-Heapify算法(这是对最大堆而言)使得当前子树成为一个二叉堆。具体而言,假设高度为h的子树均已完成二叉堆化,那么对于高度为h+1的子树,把其根节点沿着最大子节点的分枝做调整,最多需要h步完成二叉堆化。可以证明,这个算法的时间复杂度O(n)

建造最大堆伪代码Build-Max-Heap (A):
heap_length[A] ← length[A]
for ifloor(length[A]/2) downto 1 do
Max-Heapify(A, i)

合并两个二叉堆

最优方法是把两个二叉堆首尾相连放在一个数组中,然后构造新的二叉堆。时间复杂度O(log⁡nlog⁡k),其中n、k为两个堆的元素数目。

如果经常需要合并两个堆的操作,那么使用二项式堆更好,其时间复杂度O(log⁡n)


标签: 二叉堆

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议