二项堆(binomial heap)的源代码

#include "BinomialHeap.h" #include <stdio.h> #include <stdlib.h> #include <memory.h> Heap make_binomial_heap_with_keys(int keys[], int n) { Heap h = NULL, tmp = NULL; for(int i = 0; i < n; i++) { tmp = make_binomial_heap_with_key(keys[i]); if(NULL == h) { h = tmp; } else { //否则插入合并两个二项堆 h = binomial_heap_union(h, tmp); tmp = NULL; } } return h; } Heap make_binomial_heap_with_key(int key) { Heap h = NULL; h = make_binomial_heap(); h->key = key; return h; } Heap make_binomial_heap() { Heap h = NULL; if((h = (Heap) malloc (HEAP_NODE_SIZE))==NULL) { exit(-1); } memset(h, 0, HEAP_NODE_SIZE); return h; } Heap binomial_heap_union(Heap &h1, Heap &h2) { Heap h = NULL; h = binoimal_heap_merge(h1, h2); return h; } Heap binoimal_heap_merge(Heap &h1,Heap &h2) { Heap h = NULL, l = NULL, r = NULL, q = NULL, p = NULL;// h为返回堆的首地址，l为指向h1的当前根结点，r为指向h2的当前根结点, q为指向新堆p的前结点，p为指向新堆根结点 if((h1 != NULL) && (h2 != NULL)) { l = h1; r = h2; while((l != NULL) && (r != NULL)) { if(l->degree <= r->degree) { p = l; l = l->slibing; } else { p = r; r = r->slibing; } if(q == NULL) {// 找到新二项树的首根结点 q = p; h = p; } else { q->slibing = p; q = p; } } if(l != NULL) { p->slibing = l; } else { p->slibing = r; } } else if(h1 != NULL) { h = h1; } else { h = h2; } h1 = NULL; h2 = NULL; return h; } void print_binomial_heap(const Heap h) { if(NULL == h) return; printf("Print the binomial heap:\n"); _print_binomial_heap(h); printf("\n\n"); } void _print_binomial_heap(const Heap h) { if(NULL == h) return; printf("("); printf("%d", h->key); //显示其孩子 Heap p = h->child; if(NULL != p) { printf("("); _print_binomial_heap(p); printf(")"); } printf(")"); //显示其兄弟 p = h->slibing; while(NULL != p) { _print_binomial_heap(p); p = p->slibing; } } void destroy_binomial_heap(Heap &h) { if(h == NULL) return; destroy_binomial_heap(h->child); Heap s = NULL; s = h->slibing; while(s != NULL) { destroy_binomial_heap(s); s = s->slibing; } destroy_binomial_heap(h); h = NULL; } #define HEAP1_KEYS_N 10 int heap1_keys[HEAP1_KEYS_N] = {1, 7, 5, 3, 9, 10, 2, 4, 6, 8}; int main() { Heap heap1 = NULL; heap1 = make_binomial_heap_with_keys(heap1_keys, 2); print_binomial_heap(heap1); destroy_binomial_heap(heap1); return 0; }