最近找实习，复习下数据结构方面的内容。
完全二叉树有两种形态，一种是：二叉树的所有子树要么没有孩子，要么一定有左孩子。另一种是：二叉树要么没有子树，要么一定左右子树都有。
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。
最大堆和最小堆是二叉堆的两种形式。
最大堆：根结点的键值是所有堆结点键值中最大者。
最小堆：根结点的键值是所有堆结点键值中最小者。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。优先队列可以用堆来实现。
下面我们用数组来实现一个最小堆。
代码如下：
MinHeap.h
#ifndef DataStructures_MinHeap_h
#define DataStructures_MinHeap_h
struct MinHeap;
typedef struct MinHeap * MinPriorityQueue;
typedef int ElementType;
// 初始化堆
MinPriorityQueue initialize(int maxElements);
// 销毁堆
void destroy(MinPriorityQueue pqueue);
// 清空堆中的元素
void makeEmpty(MinPriorityQueue pqueue);
// 插入操作
void insert(ElementType x, MinPriorityQueue pqueue);
// 删除最小者操作，返回被删除的堆顶元素
ElementType deleteMin(MinPriorityQueue pqueue);
// 查找最小者（堆顶）
ElementType findMin(MinPriorityQueue pqueue);
// 判断堆是否为空
int isEmpty(MinPriorityQueue pqueue);
// 判断堆是否满
int isFull(MinPriorityQueue pqueue);
// 通过一个数组来建堆，相当于将用数组实现的无序树转换为堆序树
MinPriorityQueue buildHeap_insert(int *arr, int n);
MinPriorityQueue buildHeap_percolate(int *arr, int n);
// 打印堆
void printMinPriorityQueue(MinPriorityQueue pqueue);
#endif
MinHeap.c
#include
#include
#include "MinHeap.h" /* 标记节点，类似于链表中的表头节点 * 该值必须小于所有最小堆中的元素，设其值为-1 */ #define SentinelElement -1 /* * 使用数组实现堆 * * capacity 数组的最大容量 * size 数组的长度 * elements 堆中的元素存放的数组 */ struct MinHeap { int capacity; int size; ElementType *elements; // 堆的元素个数为size，实际上用来存储的数组的长度为size + 1，还包括一个sentinel元素 }; void PQueueNULLWarning() { printf("Warning: Minimum Priority Queue is NULL"); } void outOfSpaceFatalError() { printf("Fatal Error: Out of space"); abort(); } MinPriorityQueue initialize(int maxElements) { MinPriorityQueue pqueue; if (maxElements <= 0) { printf("Fail to initialize: maxElements <= 0"); return NULL; } pqueue = malloc(sizeof(struct MinHeap)); if (pqueue == NULL) outOfSpaceFatalError(); // 数组的第0个元素是个sentinel标记节点，计入数组容量中，但不计入capcaity或size中 pqueue->size = 0; pqueue->capacity = maxElements; pqueue->elements = malloc(sizeof(ElementType) * (pqueue->capacity + 1)); if (pqueue->elements == NULL) outOfSpaceFatalError(); else pqueue->elements[0] = SentinelElement; return pqueue; } void destroy(MinPriorityQueue pqueue) { if (pqueue != NULL) { // 在GNU99标准中，free(NULL)什么都不做直接返回，所以不用判断pqueue->elements是否为NULL free(pqueue->elements); free(pqueue); } } void makeEmpty(MinPriorityQueue pqueue) { if (pqueue != NULL) pqueue->size = 0; else PQueueNULLWarning(); } /* * 插入时，堆中的元素执行下滤操作 * 删除时，堆中的元素执行上滤操作 */ /* * 插入的时间复杂度为O(log N)，N为最小堆中的元素个数 * 实际上，其平均执行时间为O(1) */ void insert(ElementType x, MinPriorityQueue pqueue) { if (pqueue == NULL) PQueueNULLWarning(); if (isFull(pqueue)) { printf("Fail to insert: Priority Queue is Full"); return; } else { int i; // sentinel element在这里作为elements[0]被比较，是循环的终止条件 for (i = ++pqueue->size; x < pqueue->elements[i / 2]; i /= 2) pqueue->elements[i] = pqueue->elements[i / 2]; // 下滤操作 pqueue->elements[i] = x; } } /* * 删除操作的平均时间为O(log N) */ ElementType deleteMin(MinPriorityQueue pqueue) { if (pqueue == NULL) { PQueueNULLWarning(); return SentinelElement; } if (isEmpty(pqueue)) { printf("Fail to delete: Priority Queue is Empty"); return SentinelElement; } int i, child; ElementType minElement, lastElement; // 注意对某个节点进行上滤操作时，要判断该节点是有两个儿子还是一个儿子 minElement = pqueue->elements[1]; lastElement = pqueue->elements[pqueue->size--]; for (i = 1; i * 2 <= pqueue->size; i = child) { child = i * 2; // 节点i只有一个儿子时必有i * 2 = pqueue->size if (child < pqueue->size && pqueue->elements[child] > pqueue->elements[child + 1]) child++; if (lastElement < pqueue->elements[child]) break; else pqu