eue->elements[i] = pqueue->elements[child]; // 上滤操作 } pqueue->elements[i] = lastElement; return minElement; // 返回被删除的元素 } /* * 执行时间：O(1) */ ElementType findMin(MinPriorityQueue pqueue) { if (pqueue == NULL) { PQueueNULLWarning(); return SentinelElement; } else return pqueue->elements[1]; } int isEmpty(MinPriorityQueue pqueue) { if (pqueue == NULL) { PQueueNULLWarning(); return -1; } else return (pqueue->size == 0); } int isFull(MinPriorityQueue pqueue) { if (pqueue == NULL) { PQueueNULLWarning(); return -1; } else return (pqueue->size == pqueue->capacity); } void percolateDown(int *arr, int len, int i) { int n = len - 1; int tmp; if (i * 2 == n && arr[i] > arr[n]) // 只有左儿子的节点，并且左儿子比本节点的值要小，交换 { tmp = arr[i]; arr[i] = arr[n]; arr[n] = tmp; } else // 有两个儿子的节点 { if (arr[i * 2] > arr[i * 2 + 1]) // 右儿子较小 { if (arr[i] > arr[i * 2 + 1]) // 如果本节点比右儿子大，交换 { tmp = arr[i]; arr[i] = arr[i * 2 + 1]; arr[i * 2 + 1] = tmp; } } else // 左儿子较小 { if (arr[i] > arr[i * 2]) // 如果本节点比左儿子大，交换 { tmp = arr[i]; arr[i] = arr[i * 2]; arr[i * 2] = tmp; } } } } MinPriorityQueue buildHeap_percolate(int *arr, int n) { if (arr == NULL) { printf("Error: Array is NULL"); return NULL; } MinPriorityQueue pqueue; pqueue = malloc(sizeof(struct MinHeap)); if (pqueue == NULL) outOfSpaceFatalError(); ElementType *elements = malloc(sizeof(ElementType) * (n + 1)); if (elements == NULL) outOfSpaceFatalError(); int i; for (i = 1; i <= n; i++) elements[i] = arr[i - 1]; elements[0] = SentinelElement; for (i = n / 2; i > 0; i--) percolateDown(elements, n + 1, i); pqueue->elements = elements; pqueue->size = n; pqueue->capacity = n * 2; return pqueue; } /* * 通过n次插入元素建立堆，由于每次插入的平均执行时间为O(1)，所以建堆平均时间为O(N) */ MinPriorityQueue buildHeap_insert(int *arr, int n) { MinPriorityQueue pqueue; if (arr == NULL) { printf("Array is NULL, fail to build heap"); return NULL; } pqueue = initialize(n * 2); for (int i = 0; i < n; i++) insert(arr[i], pqueue); return pqueue; } void printMinPriorityQueue(MinPriorityQueue pqueue) { if (pqueue == NULL) { PQueueNULLWarning(); return; } if (pqueue->elements == NULL) { printf("Fail to print: Elements of priority queue is NULL"); return; } if (isEmpty(pqueue)) { printf("Empty Prioirty Queue\n"); return; } printf("Priority Queue\n"); for (int i = 1; i <= pqueue->size; i++) printf("Element[%d] = %d\n", i, pqueue->elements[i]); printf("\n"); }
建堆的测试代码：
#include
#include
#include "MinHeap.h" int main(int argc, const char * argv[]) { int a[5] = {5, 4, 3, 2, 1}; MinPriorityQueue pqueue_ins = buildHeap_insert(a, 5); MinPriorityQueue pqueue_per = buildHeap_percolate(a, 5); printMinPriorityQueue(pqueue_ins); printMinPriorityQueue(pqueue_per); return 0; }
分别使用插入和下滤两种方式建堆，所以建立的结果是不同的，输出如下：
Priority Queue
Element[1] = 1
Element[2] = 2
Element[3] = 4
Element[4] = 5
Element[5] = 3
Priority Queue
Element[1] = 1
Element[2] = 5
Element[3] = 3
Element[4] = 2
Element[5] = 4
最大堆实现类似。