最大堆（最小堆）

  1 #define MAX_ELEMENTS 200 /* maximun heap size+1 */
  2 #define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
  3 #define HEAP_EMPTY(n) (!n)
  4 typedef struct {
  5   int key;
  6   /* other fields */
  7 } element;
  8 element heap[MAX_ELEMENTS];
  9 int n = 0;
 10 
 11 //插入函数
 12 void insert_max_heap(element item, int *n)
 13 {
 14   /*insert item into a max heap of current size *n */
 15   int i;
 16   if (HEAP_FULL(*n)) {
 17     fprintf(stderr, "The heap is full. \n");
 18     exit(1);
 19   }
 20   i = ++(*n); //把值放入数组最后
 21   while ((i != 1) && (item.key > heap[i/2].key)) {
 22 //如果没到根节点，切当前节点值大于其父节点值，就把父节点下移
 23     heap[i] = heap[i/2];
 24     i /= 2; //找到父节点索引继续循环
 25   }
 26   heap[i] = item; //循环结束时候的位置就是真正要插入的位置
 27 }
 28 //这个插入函数可以用下面的move_up函数重写，要插入值放在数组最后，然后不停move_up即可
 29 
 30 //删除最大值
 31 element delete_max_heap(int *n)
 32 {
 33   /* delete element with the highest key from the
 34      heap 
 35   */
 36   int parent, child;
 37   element item, temp;
 38   if (HEAP_EMPTY(*n)) {
 39     fprintf(stderr, "The heap is empty.\n");
 40     exit(1);
 41   }
 42   /* save value of the element with the hightest key */
 43   item = heap[1];
 44   /* use last element in heap to adjust heap */
 45   temp = heap[(*n)--]; //删除最后一个值临时保存起来
 46   parent = 1;
 47   child = 2;
 48   while (child <= *n) { //子节点索引小于等于最大长度才继续
 49     /* find the larger child of the current parent */
 50     if ((child < *n) && (heap[child].key < heap[child+1].key)) {
 51 //找出两个儿子中较大的值
 52         child++;
 53     }
 54     if (temp.key >= heap[child].key) break; //移动的值大于当前值，结束循环
 55     heap[parent] = heap[child];//根节点不再了，把儿子中较大的移动上去
 56     parent = child;
 57     child *= 2;
 58   }
 59   heap[parent] = temp;
 60   return item;
 61 }
 62 //这个函数也是可以用下面的move函数改写，删除第一个值（最大值），然后吧最后一个值放入最大值的位置，然后不停move_down即可
 63 
 64 //改变任意值的优先级
 65 //如果变大，就move_up，变小，就move_down
 66 void change_element_value(element item, int index, int *n)
 67 {
 68   if ((index <= 0) || (index > *n)) {
 69     fprintf(stderr, "No this element.\n");
 70     exit(1);
 71   }
 72   if (item.key = heap[index].key) {
 73     return;
 74   }
 75   if (item.key > heap[index].key) {
 76     heap[index] = item;
 77     move_up(index);
 78   }else {
 79     move_down(index, n);
 80   }
 81 }
 82 
 83 void swap_element(int m, int n)
 84 {
 85   element temp;
 86   temp = heap[m];
 87   heap[m] = heap[n];
 88   heap[n] = temp;
 89 }
 90 void move_up(int i)
 91 {
 92   /* need check i's range, I don't do it at this. */
 93   while (i != 1) {
 94     if (heap[i] > heap[i/2]) {
 95       swap(i, i/2);
 96       i /= 2;
 97     }else {
 98       break;
 99     }
100   }
101 }
102 void move_down(int i, int *n)
103 {
104   int next;
105   while (2*i <= *n) {
106     next = 2*i;
107     if (next < *n && heap[next].key < heap[next+1].key) {
108       next += 1;
109     }
110     if (heap[i] < heap[next]) {
111       swap(i, next);
112       i = next;
113     }else {
114       break;
115     }
116   }
117 }
118 
119 //创建最大堆
120 //这个函数原理简单，是遍历给定的那组数字，然后一个一个的insert，
121 //最后就得到了最大堆
122 void make_heap1(int a[], int length, int *n)
123 {
124   /* insert one by one */
125   int i = 0;
126   for ( ; i < length; ++i) {
127     element temp;
128     temp.key = a[i];
129     insert_max_heap(temp, *n);
130   }
131 }
132 
133 //这个函数稍微复杂点：实在给定数组之上，直接调整位置，来构成最大堆（最大堆数组存储）
134 //原理：假设数组足够大，不会越界。把第0位的值存入最后。因为最大堆不用第0位。
135 //然后从数组最后开始遍历，先找到最后一个值的父节点，然后move_down构造最小堆
136 //从后往前，依次重复这个过程，知道第一个值，最大堆完成（有点递归的意思）
137 void make_heap2(int a[], int length)
138 {
139   a[length] = a[0];
140   int i;
141   for (i = length; i >= 1; --i) {
142     if (i/2 >= 1) {
143       move_down(i/2, length);
144     }
145   }
146 }