堆的性质：堆是一棵完全二叉树，它有最大堆和最小堆之分，这里只分析最大堆！（最小堆与最大堆类似）  就是所有的子节点都小于根节点的完全二叉树

堆的几种操作（数组实现）： 其中 len 表示 数组长度，headsize表示堆的长度

其中堆的左节点编号

int LEFT(int i ){  return i*2;}

堆的右节点编号：

int RIGHT(int i ){   return i*2 +1;}

堆的头结点编号

int PARENT(int i ){   return i/2;}

 

1.保持堆的性质：

void MAX_HEAPIFY(int A[],int i){  int l = LEFT(i);  int r = RIGHT(i);  int largest;  if( l<= heapsize && A[l] > A[i])      largest = l;  else largest = i;  if(r <= heapsize && A[r] > A[largest])     largest = r;  //找出本节点以及其儿子节点最大的值的编号  if(i != largest)    {      int temp = A[i];      A[i] = A[largest];      A[largest] = temp;      MAX_HEAPIFY(A,largest);//子树可能交换后不保持性质，使起保持性质    }}

2.建堆   O( nlgn)

void BUILD_MAX_HEAP(int A[]){   heapsize = len;   for(int i = len/2 ;i >= 1;i --)      MAX_HEAPIFY(A,i);}

3.堆排序  O(nlgn)

void HEAPSORT(int A[]){   BUILD_MAX_HEAP(A);   for(int i = len ;i >= 2;i --)     {       int temp = A[1];       A[1] = A[i];       A[i] = temp;       heapsize = heapsize - 1;            }}

4.找出堆的最大值   O(1)

int HEAP_MAXIMUM(int A[]){   return A[1];}

5.找出堆的最大值并删除它  O(lgn)

int HEAP_EXTRACT_MAX(int A[]){   if(heapsize < 1)      {        printf("heap underflo");        exit(0);      }   int max = A[1];   A[1] = A[heapsize];   heapsize = heapsize - 1;   MAX_HEAPIFY(A,1);   return max;}

6.将某元素的的值增加到某值  O(lgn)

1 void HEAP_INCREASE_KEY(int A[],int i,int key) 2 { 3   if(key < A[i]) 4     { 5        printf("new key is smaller than current key"); 6        exit(0); 7     } 8   A[i] = key; 9   while(i > 1 and A[PARENT(i)] < A[i] )10    {11      int temp = A[PARENT(i)];12      A[PARENT(i)] = A[i];13      A[i] = temp;14      i = PARENT(i);15    }//向上更新16 17 }

7.加入到某值    O(lgn)

void MAX_HEAP_INSERT(int A[],int key){    heapsize = heapsize +1;    A[heapsize] = INT_MIN;    HEAP_INCREASE_KEY(A,heapsize,key);}

其中堆排序没有响应的删除算法，只有朴素思路。。