大根堆，小根堆，堆排序木

大根堆: 根节点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). 堆排序思路：在待排序的元素中建立大根堆，每次都把最大的取出来，这样就完成了排序。未完，待续。。。。

大根堆，小根堆，堆排序 木

大根堆，小根堆，堆排序木