二叉堆 - 最小堆

二叉堆：一般我们拿来用的就是最大堆和最小堆。

最小堆：每个节点的值比它的左右子节点的值要大。

代码实现如下：参考Mark Allen Weiss《数据结构和算法分析》（第二版）

1 #include <cstdio>
  2 #include <cstdlib>
  3 
  4 #define MIN (1<<(sizeof(int)*8-1))
  5 
  6 typedef int Item;
  7 typedef struct HeapStruct* heap;
  8 
  9 struct HeapStruct {
 10     int capacity;  // capacity的大小为堆的元素加1。 
 11     int size;      // size指向堆中最后一个元素，size=0时堆为空 
 12     Item* items;   // items的第一个元素存放sentinel，其余元素存放堆中内容。 
 13 };
 14 // 初始化堆的三个参数 
 15 heap
 16 InitHeap(int maxItems)
 17 {
 18     heap h;
 19     
 20     h = (heap)malloc(sizeof(struct HeapStruct));
 21     if (h == NULL) {
 22         printf("out of space.\n");
 23         return NULL;
 24     }
 25     
 26     h->items =(Item*)malloc((maxItems+1)*sizeof(Item)); // 用h->items[0]来存放sentinel 
 27     if (h->items == NULL) {
 28         printf("out of space.\n");
 29         return NULL;
 30     }
 31     
 32     h->capacity = maxItems;
 33     h->size = 0;
 34     h->items[0] = MIN;
 35     
 36     return h;
 37 }
 38   
 39 int
 40 IsFull(heap h)
 41 {
 42     if (h->size == h->capacity) {
 43         return 1;
 44     } else {
 45         return 0;
 46     }
 47 }
 48 
 49 int
 50 IsEmpty(heap h)
 51 {
 52     if (h->size == 0) {
 53         return 1;
 54     } else {
 55         return 0;
 56     }
 57 }
 58   
 59 Item
 60 FindMin(heap h)
 61 {
 62     return h->items[1];
 63 }
 64 // 向最小堆插入元素。  
 65 void
 66 Insert(Item item, heap h)
 67 {
 68     if (IsFull(h)) {
 69         printf("Insert failed. Because the heap is full.\n");
 70         return;
 71     }
 72     // percolate up，将item往上，一步一步放到合适的地方。
 73     int i; 
 74     for (i = ++h->size; h->items[i/2] > item; i /= 2) {
 75         h->items[i] = h->items[i/2];
 76     }
 77     h->items[i] = item;
 78 }
 79 // 在最小堆中删除元素。 返回最小值。 
 80 Item
 81 DeleteMin(heap h)
 82 {
 83     if (IsEmpty(h)) {
 84         printf("Delete failed. Because the heap is empty.\n");
 85         return h->items[0];
 86     }
 87     
 88     Item minItem = h->items[1];
 89     Item lastItem = h->items[h->size--]; // 此函数目的就是把lastItem放到合适位置 
 90     // percolate down，将lastItem往下，一步一步往下寻找合适的地方。
 91     int i, child;
 92     for (i = 1; 2*i <= h->size; i = child) {
 93         child = 2 * i;
 94         // 将child放在左右子树中较小的那个位置上
 95         if (child != h->size && h->items[child] > h->items[child+1]) {
 96             child++;
 97         }
 98         
 99         if (lastItem > h->items[child]) {
100             h->items[i] = h->items[child];
101         } else {
102             break;
103         }
104     }
105     h->items[i] = lastItem;
106     return minItem;
107 }
108 // 以插入的方式来建堆。复杂度为O(NlogN)，因为有N个元素，每次插入花费logN时间。      
109 void
110 BuildHeap(heap h, Item arr[], int len)
111 {
112     for (int i = 0; i < len; i++) {
113         Insert(arr[i], h);
114     }
115 }
116 // 以下滤的方式来建堆（对已有的数组进行排序，使之符合最小堆的堆序heap order）。
117 // 参数i为数组对应的二叉堆的内部节点，下滤操作将之放到比左右子节点都小的位置上。 
118 void
119 PercDown(heap h, int i) 
120 {
121     int child;
122     int tmp;
123     
124     for (tmp = h->items[i]; 2*i <= h->size; i = child) {
125         child = 2*i;
126         if (child != h->size && h->items[child] > h->items[child+1]) {
127             child++;
128         }
129         if (tmp > h->items[child]) {
130             h->items[i] = h->items[child];
131         } else {
132             break;
133         }
134     }
135     h->items[i] = tmp;
136 }
137 
138 int 
139 main(int argc, char** argv)
140 {
141     int arr[6] = {17, 11, 2, 23, 5, 7};
142     
143     heap h;
144     h = InitHeap(6);
145     //BuildHeap(h, arr, 6);
146     // build heap
147     for (int i = 0; i < 6; i++) {
148         h->items[++h->size] = arr[i];
149         
150     }
151     for (int i = 6/2; i > 0; i--) {
152         PercDown(h, i);
153     }
154     
155     for (int i = 1; i <= h->size; i++) {
156         printf("%d\t", h->items[i]);
157     }
158     printf("\n");
159     
160     // test DeleteMin, out put a sorted array
161     int sortedArr[6] = {0};
162     for (int i = 0; i < 6; i++) {
163         sortedArr[i] = DeleteMin(h);
164     }
165     for (int i = 0; i < 6; i++) {
166         printf("%d\t", sortedArr[i]);
167     }
168     printf("\n");
169     
170     system("pause");
171     
172     return 0;
173 }      

转载于:https://www.cnblogs.com/nipan/p/4058202.html