Chinaunix首页 | 论坛 | 博客
  • 博客访问: 583804
  • 博文数量: 102
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 1748
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-23 15:42
个人简介

寻找严肃、沉默和专注的力量。

文章分类

全部博文(102)

文章存档

2015年(26)

2014年(8)

2013年(68)

分类: C/C++

2013-05-29 19:32:33

本为转载自:http://blog.csdn.net/super_chris/article/details/4581900

堆,是一棵完全二叉树,根的值大于左右子树中所有结点的值,左右子树也是堆,除此之外,对其它元素之间的大小关系(如左右子树之间元素大小关系)没有要求。

 

这是大根堆,如果把“大于”换成“小于”,就是小根堆,这里都以大根堆为例。

 

由于堆是完全二叉树,所以可以用数组来模拟,在数据结构上算是比较简单(所以才敢学啊,以前未考虑到它是完全二叉树,以为要用到二叉链表,迟迟没敢看。。)。

 

用数组模拟二叉树(当然也包括堆)的话,如果根节点的下标为0的话,则对于每个结点i,其左孩子下标为2*i+1;其右孩子下标为2*i+2。

堆有两个基本操作:插入元素和删除元素。

 

插入: 将待插入元素添加到数组末尾,然后依次向上比较,如果该结点大于父亲节点,就与父节点交换,这样就构成局部大根堆,一直到该结点小于父节点位置,便完成了结点的插入操作。

 

删除: 要删除某元素,可以将数组的大小缩小一,然后用数组的末尾元素代替待删除元素,然后将缩小后的数组重新调整为堆,便完成了结点的删除操作。

 

堆有一个重要的应用就是堆排序,下面介绍堆排序。

 

堆排序的思想很简单,仍然以大根堆为例。

 

将待排序区分为无序区和有序区,无序区在前,有序区在后。未排序前无序区为整个待排序区间,没有有序区。

 

排序的过程是,不断地将无序区构造成一个大根堆,这样无序区中的最大元素便被放置在了数组的最前面即根的位置,然后将无序区的第一个元素与最后一个元素交换,此动作将无序区的长度缩小一,将有序区的长度扩大一,即有序区前进一,无序区向前退一。然后将新的无序区(由于根节点的变化,此时很可能已经不是大根堆)重新调整为大根堆,等待下一次的交换。如此往复,不断地将无序区的最大元素添加到有序区的前面,同时缩小无序区,直到有序区占满待排序区为止。

 

这样,还剩下两个问题: 1.如何将一个交换后的无序区调整为大根堆; 2.如何在排序之前建立那个初始的大根堆。

 

而第二个问题是可以通过第一个问题的解决而解决的。这个稍后再谈,现在先看第一个问题。

 

由于进行元素交换前,无序区是一个大根堆,即左子树和右子树都是大根堆,所以根节点变化后左右子树仍然都是大根堆,无序区里的最大元素一定在新根节点、左右子树的根节点这三个结点里。先存储新的根节点的值以待后用。如果新的根结点最大,说明已经是大根堆,调整完毕;否则比较左右子树根节点,找出较大的,它是无序区现存的最大元素,应该作为新的大根堆中的根,所以将此节点上调至根节点位置,接下来就只需要调整此结点原来所在的子树为大根堆即可(因为大根堆对左右子树之间元素的大小关系没有要求!)。

 

这是一个迭代的过程,当某一个需要调整的子树调整前就已经是大根堆(待调整的根节点比左右子树根节点都大)时,或者下标已经超出无序区范围时,迭代过程结束,无序区已经调整为大根堆。

 

这就是调整一个左右子树都为大根堆的完全二叉树为大根堆的过程。

 

那么如何利用此过程建立初始大根堆呢? 若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标[n/2]开始的元素均为大根堆。于是只要从[n/2]-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆(这就可以调用我们上面讨论的调整为大根堆的方法了)。一直到下标为0的结点,就完成了初始大根堆的建立。 堆排序用到的函数有两个:1个将左右子树都为大根堆的完全二叉树调整为大根堆的调整函数;1个反复调用此调整函数来进行排序的排序函数。

 

下面给出代码,根据调整时被调整结点的行为,将调整函数称为渗透(Sift)函数。

 


[cpp] view plaincopy
  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. template  
  6. void Sift(T* heap,int start,int end)    //start和end标示无序区  
  7. {  
  8.     T temp = heap[start];   //记录  
  9.     int parent = start;  
  10.     int child = 2*start+1;  
  11.     while (child<=end)  
  12.     {  
  13.         if(child
  14.             child++;  
  15.         if(heap[child]>temp)  
  16.         {  
  17.             heap[parent]=heap[child];  
  18.             parent = child;  
  19.             child = 2*child+1;  
  20.             continue;  
  21.         }  
  22.         else  
  23.             break;  
  24.     }  
  25.     heap[parent] = temp;  
  26. }  
  27.   
  28. template   
  29. void MakeHeap(T* heap,int Size)  
  30. {  
  31.     int end;  
  32.     for(int start = Size/2-1;start>=0;start--)  
  33.         Sift(heap,start,Size-1);  
  34. }  
  35.   
  36. template   
  37. void HeapSort(T* heap,int Size)  
  38. {  
  39.     MakeHeap(heap,Size);  
  40.     T temp;  
  41.     for (int i = Size-1;i >= 0;i--)  
  42.     {  
  43.         temp = heap[i];  
  44.         heap[i] = heap[0];  
  45.         heap[0] = temp;  
  46.         Sift(heap,0,i-1);  
  47.     }  
  48.     for (int i = 0;i < Size;i++)  
  49.     {  
  50.         cout<
  51.     }  
  52. }  
  53.   
  54. int main()  
  55. {  
  56.     int num[10] = {1,4,3,8,9,0,2,7,5,6};  
  57.     HeapSort(num,10);  
  58. }  


 

 

本质上,堆排序就是选择排序,每次选择当前无序区最大的放入有序区。

对于直接选择排序,选择的过程要进行遍历,一次选择过程的复杂度为O(n)。堆排序利用堆的性质和二叉树的结构使得每次选择的复杂度降低为O(logn),从而有效地改进了选择排序。

阅读(1105) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

iWonderLinux2013-05-29 19:33:24

这个讲得也很清楚:http://blog.csdn.net/morewindows/article/details/6709644