Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1800308
  • 博文数量: 438
  • 博客积分: 9799
  • 博客等级: 中将
  • 技术积分: 6092
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-25 17:25
文章分类

全部博文(438)

文章存档

2019年(1)

2013年(8)

2012年(429)

分类: C/C++

2012-04-05 13:19:19

是一个数据结构,它是一棵完全二叉树。(完全树除最后一层外每层都是 填满的,而最后一层从左往右开始填直至到最后一个结点。)在这棵完全树中,每个父结点的值都不小于它的两个子结点的值(最大堆,也叫大根堆。如果小根堆则 每个父结点的值不小于它的两个子结点)。通常我们用数组表示堆,并用一个数值heapSize来表示数组最前面heapSize个元素构成了一个堆:

对于数组A,A[1]是堆的根。对于某个下标为i的结点,它的父结点、左儿子和右儿子的下标都可以简单计算出来:


  1. PARENT(i) {
  2.     return floor(i/2);
  3. }

  4. LEFT(i) {
  5.     return 2*i;
  6. }

  7. RIGHT(i) {
  8.     return 2*i + 1;
  9. }

保持堆的性质

有时一个结点的左子树和右子树都是堆,但该结点本身却小于它的某个子结点,于是违反了堆的性质。我们可以通过下面的过程来使它变为一个堆:把违反堆性质的结点与值更大的子结点交换,再递归保持交换后的产生的新子树的堆性质。

相应的保持堆的伪代码:


  1. MAX_HEAPIFY(A, i) {
  2. 1   l = LEFT(i);
  3. 2   r = RIGHT(i);
  4. 3   if l ≤ A.heaSize and A[l] > A[i]
  5. 4     largest = l;
  6. 5   else
  7. 6     largest = i;
  8. 7   if r ≤ A.heapSize and A[r] > A[largest]
  9. 8     largest = r;
  10. 9   if largest ≠ i {
  11. 10     swap(A[i], A[largest]);
  12. 11     MAX_HEAPIFY(A, largest);
  13. 12  }
  14. }

MAX_HEAPIFY的效率分析:一棵有n个元素,根结点为i的堆,其中每次交换父结点与子结点的开销为Ө(1)。它子树大小至多为2/3*n(在最坏情况发生在最底层恰好半满的时候),所以它的运行时间可以表示为:
T(n) ≤ T(2*n/3) + Ө(1)
根据主方法条件2可以得到T(n) = O(lg(n))。换而言之,保持堆的运行时间为O(lg(n)),或者说保持高度为h的堆的运行时间为O(h)


建堆

对于一个数组A[1...n],我们可把它看成一个违反堆性质的完全二叉树。在建堆时,从最下层的子树开始,使用前面所述的保持堆的算法,使得所有的子树都是一个堆,直至整棵二叉树A[1...n]就成为一个堆。
建(最大)堆的伪代码如下:


  1. BUILD_MAX_HEAP(A) {
  2. 1     A.heapSize = A.length;
  3. 2     for i = floor(A.length/2) downto 1
  4. 3          MAX_HEAPIFY(A, i);
  5. }

这个算法直观上看上去的运行时间为O(n*lg(n)),因为MAX_HEAPIFY的运行时间为O(lg(n)),而且MAX_HEAPIFY运行了O(n)次。但是这个上界不够紧确,下面更深入地分析建堆的效率:
一个元素数量为n的堆高度为floor(lg(n)),同时对于任意高度为h的子树,至多有ceiling(n/(2^(h+1)))个结点,而MAX_HEAPIFY作用在高度为h的结点上的时间为O(h),所以总的建堆的运行时间可以表示为:
T(n) ≤ ∑ ceiling(n/(2^(h+1))) * O(h) = O(n*∑ h/2^h)
因为∑ h/2^h = 2 (等比数列求和),所以上式T(n) ≤ O(n*2) = O(n)。综上所述,建堆的运行时间为O(n)


堆排序算法

在 基于数组A[1...n]建堆后,就可以用这个堆进行排序了。我们把数组A看成两部份,左侧为堆结构,右侧为排好序的序列。因为一个(最大)堆的根结点是 最大元素,所以我们每次把堆的根结点提取出来放入到数组A右侧的有序数列的最左边。每次提取根后,堆的大小减一,而右侧有序数列的大小加一。当整个堆都被 转移到有序数列的部分时,整个数组也就完成排序了。在每次转移堆的根结点时,需要用堆的最右元素来充当新的根,但这样可能会违反堆的性质,所以需要保持堆 的操作。下面是伪代码:


  1. HEAPSORT(A) {
  2. 1    BUILD_MAX_HEAP(A);
  3. 2    for i = A.length downto 2 {
  4. 3       swap(A[1], A[i]);
  5. 4       A.heapSize = A.heapSize - 1;
  6. 5       MAX_HEAPIFY(A, 1);
  7. 6    }
  8. }

堆排序算法的运行时间为O(n*lg(n))

优先级队列

虽然堆排序算法很漂亮,但在实际中它往往比不上快速排序算法。仅管如此,堆数据结构仍然有很大的作用,比如实现优先级队列(priority queue)。与堆一样,优先级队列也有两种:最小优先级队列最大优先级队列

(最大)优先级队列每次取元素时都返回优先级最高的元素,它包含以下操作:
INSERT(S, x):把元素x插入集合S。
MAXIMUM(S):返回S中的最大元素。
EXTRACT_MAX(S):去掉并返回S中的最大元素。
INCREASE_KEY(S, x, k):将元素x的关键字的值增加到k,这里k值不能小于x的原关健字的值。

下面给出以上操作的伪代码:


  1. HEAP_MAXIMUM(A) {
  2. 1   return A[1];
  3. }

HEAP_MAXIMUM的运行时间为O(1)。



  1. HEAP_EXTRACT_MAX(A) {
  2. 1   if A.heapSize < 1
  3. 2     error("heap underflow");
  4. 3   max = A[1];
  5. 4   A[1] = A[A.heapSize];
  6. 5   A.heapSize = A.heapSize - 1;
  7. 6   MAX_HEAPIFY(A, 1);
  8. 7   return max;
  9. }

HEAP_EXTRACT_MAX的运行时间为O(lg(n)),主要消耗在MAX_HEAPIFY的操作上。



  1. HEAP_INCREASE_KEY(A, i, key) {
  2. 1   if key < A[i]
  3. 2     error("new key is smaller than current key");
  4. 3   A[i]=key;
  5. 4   while i>1 and A[PARENT(i)]<A[i] {
  6. 5     swap(A[i], A[PARENT(i)]);
  7. 6     i = PARENT(i);
  8. 7   }
  9. }

HEAP_INCREASE_KEY的运行时间为O(lg(n)),因为要执行lg(n)(堆的高度)次交换操作



  1. MAX_HEAP_INSERT(A, key) {
  2. 1    A.heapSize = A.heapSize + 1;
  3. 2    A[A.heapSize] = -;
  4. 3    HEAP_INCREASE_KEY(A, A.heapSize, key);
  5. }

MAX_HEAP_INSERT的运行时间为O(lg(n)),主要消耗在HEAP_INCREASE_KEY的操作上。
阅读(2121) | 评论(0) | 转发(7) |
给主人留下些什么吧!~~