堆的相关操作-最大堆，最小堆，堆排序，优先队列等

最近复习了一下堆的操作，做一个记录。

#include
#include "common.h"

#define LEFT(i) ((i)<<1|1)
#define RIGHT(i) (LEFT(i) + 1)
#define PARENTS(i) ((i)/2)

// 最大堆
void max_heapfy(int *a, int i, int size)
{
 int larg;
 int left = LEFT(i);
 int right = RIGHT(i);

 if (left < size && a[left] > a[i]) 
  larg = left;
 else
  larg = i;

 if (right < size && a[right] > a[larg])
  larg = right;

 if (larg != i) {
  swap(a, i, larg);
  max_heapfy(a, larg, size);
 }
}

void max_heapfy_loop(int *a, int i, int size)
{
 int larg;
 int left = LEFT(i);
 int right = RIGHT(i);

 if (left < size && a[left] > a[i]) 
  larg = left;
 else
  larg = i;

 if (right < size && a[right] > a[larg])
  larg = right;

 while (larg != i) {
  swap(a, i, larg);
  i = larg;
  left = LEFT(larg);
  right = RIGHT(larg);

  if (left < size && a[left] > a[i]) 
   larg = left;
  else
   larg = i;

  if (right < size && a[right] > a[larg])
   larg = right;
 }
}

void build_maxheap(int *a, int len)
{
 int i;
 
 for (i = (len+1)/2-1; i>=0; i--) {
  max_heapfy(a, i, len); 
 } 
}

void heap_sort(int *a, int len)
{
 int i;
 int size = len;

 build_maxheap(a, len); 

 for (i=size-1; i>=1; i--) {
  swap(a, 0, i);
  size--;
  max_heapfy_loop(a, 0, size);
 }
}

/*
 * 最小堆
 */
void min_heapfy(int *a, int i, int size)
{
 int min;
 int left = LEFT(i);
 int right = RIGHT(i);

 if (left < size && a[left] < a[i]) 
  min = left;
 else
  min = i;

 if (right < size && a[right] < a[min])
  min = right;

 if (min != i) {
  swap(a, i, min);
  min_heapfy(a, min, size);
 }
}

void build_minheap(int *a, int len)
{
 int i;
 for (i=(len+1)/2-1; i>=0; i--) {
  min_heapfy(a, i, len);
 }
}

/* 按从小到大的顺序排序 */
void heap_sort_min(int *a, int len)
{
 int i;
 int size = len;

 build_minheap(a, len); 
 
 for (i=size-1; i>=1; i--) {
  swap(a, 0, i);
  size--;
  min_heapfy(a, 0, size);
 }
}

 

/*
 * 最大优先队列
 */
/* 取最大值 */
int heap_maxinum(int *a, int len)
{
 return a[0];
}

/*
 * 1, 取第一个元素，就是最大值
 * 2, 把最后一个元素赋给第一个元素，把堆的大小-1，再最大化堆
 */
int heap_extract_max(int *a, int *max, int len)
{
 int size = len;

 if (size < 1) return -1;
 *max = a[0];
 a[0] = a[size-1]; 
 size -= 1;
 max_heapfy_loop(a, 0, size); 
 return max;
}

int main(int argc, char *argv[])
{
 int a[10] = {9,14,10,8,7,3,16,2,4,1};
 printarr(a, 10);
 //build_maxheep(a, 10);
 //build_maxheap_useloop(a, 10);
 printarr(a, 10);
 heap_sort(a, 10);
 printarr(a, 10);
 heap_sort_min(a, 10);
 printarr(a, 10);
 return 0;
}