大根堆，小根堆，堆排序
大根堆，小根堆，堆排序
大根堆: 根节点value不小于子节点的value，满足这条性质的二叉树即为大根堆。
小根堆：根节点value不大于子节点的value，满足这条性质的二叉树即为小根堆。
从大根堆的定义可知：在大根堆里要得到最大值只需o(1)的时间。所以很明显，大根堆可以求最大值和维护前k小的数。注意是前k小的数，不是前k大的数，因为当前要插入到堆里的数可以直接和堆里最大值考虑，如果比堆里最大的都还要小，那就那这个值放到堆里，这样就维护了前k小的数。
如果k很大的话，要划分为很多个堆。小根堆和大根堆相反。
堆的操作主要有：
bool isEmpty(int *a); // 判断堆是否为空
bool isFull(int *a); //判断堆是否为满
int top(int *a);// 返回堆顶元素
void pop(int *a);//删除堆顶元素
pop是删除堆顶元素，直接把最后面那个元素的值赋给堆顶，同时元素个数减一，然后是调整堆。
void push(int *a，int);//插入元素
push之前要判断空间是否为满，直接把value放到堆最后，然后是调整堆。
代码：
View Code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 #define maxSize 200008<<2
8 int heap[maxSize];
9
10 bool isEmpty( int * a);
11 bool isFull( int * a);
12 int top( int * a);
13 void pop( int * a);
14 void push( int *a, int );
15
16 template <typename T>
17 void Swap( T& a, T& b)
18 {
19 T tmp = a; a = b; b = tmp;
20 }
21
22 // 判空
23 bool isEmpty( int * a){
24 return a[ 0 ]<= 0 ? true : false ;
25 }
26 //
27 bool isFull( int * a){
28 return a[ 0 ]+ 1 >=maxSize? true : false ;
29 }
30
31 int top( int * a){
32 if (isEmpty(a) ) {
33 puts( " since for the heap is empty, the operation is illegel! " );
34 exit( 0 );
35 }
36 return heap[ 1 ];
37 };
38
39 // 调整堆，自上往下
40 void adjust( int * a ) {
41 int i = 1 ;
42 while ( i <= a[ 0 ] ){
43 if ((i<< 1 | 1 ) <= a[ 0 ] ) // 存在左右子树。
44 {
45 if (a[i<< 1 ] > a[i] && a[i<< 1 ]>a[i<< 1 | 1 ]){
46 Swap(a[i<< 1 ], a[i]); i <<= 1 ;
47 } else if (a[i<< 1 | 1 ] > a[i]) {
48 Swap(a[i<< 1 | 1 ], a[i]);
49 i = i<< 1 | 1 ;
50 } else break ;
51
52 } else if ( (i<< 1 ) <= a[ 0 ] ) { // 只存在左子树
53 if (a[i<< 1 ] > a[i]){
54 Swap(a[i<< 1 ], a[i]); i <<= 1 ;
55 } else break ;
56
57 } else break ;
58 }
59 }
60
61 void pop( int * a){
62 if (isEmpty(a) ) {
63 fprintf(stderr, " the heap is empty! " );
64 exit( 0 );
65 }
66 a[ 1 ] = a[a[ 0 ]-- ];
67 adjust(a);
68 }
69
70 void outPut( int * a){
71 puts( " ***********************************\n " );
72 if (isEmpty(a) ) puts( " the heap is empty! " );
73 else
74 {
75 for ( int i= 1 ; i<=a[ 0 ]; ++ i)
76 printf( " %d %d\n " , i, a[i]);
77 }
78 puts( " ***********************************\n " );
79 }
80
81 void push( int *a, int value){
82 if (isFull(a) ) {
83 fprintf(stderr, " the heap is full!\n " );
84 return ;
85 }
86 a[++a[ 0 ] ] = value;
87 int i = a[ 0 ]; // 调整堆,自下而上
88 while (i > 1 && a[i] > a[i/ 2 ]) {
89 Swap(a[i], a[i/ 2 ]); i >>= 1 ;
90 }
91 };
92
93 int main()
94 {
95 heap[ 0 ] = 0 ; // 记录元素个数；
96 printf( " push five intgers: " );
97 for ( int i= 0 , tmp; i< 5 ; ++ i ) {
98 scanf ( " %d " , & tmp);
99 push(heap, tmp); // 插入元素
100 }
101 outPut(heap); // 输出堆
102
103 int maxx = top(heap); // 取出堆的最大值
104 printf( " the maxx in current tree is %d \n " , maxx);
105
106 // 删除堆顶(最大值)
107 printf( " delete tha top node.\n " );
108 pop(heap);
109 outPut(heap);
110
111 printf( " 输入一个元素进行插入操作： " );
112 int tmp; scanf( " %d " , & tmp);
113 push(heap, tmp);
114 outPut(heap);
115
116 printf( " clear the heap.\n " );
117 while (! isEmpty(heap) ) pop(heap);
118 printf( " the size of the heap is %d\n " , heap[ 0 ]);
119
120 system( " pause " );
121 };
堆排序： 向大根堆中插入和删除元素的时间都是0(logn)，根据这两个操作的时间，可以知道堆排序的时间复杂度为n*log(n). 堆排序思路： 在待排序的元素中建立大根堆，每次都把最大的取出来，这样就完成了排序。未完，待续。。。。
分类: 数据结构
标签: 数据结构 , 大根堆 , 小根堆 , 堆排序
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息