数据结构-二叉堆

二叉堆（优先队列）具有结构性和堆序性

    结构性为：二叉堆是一棵完全被填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。二叉堆可以用数组表示，对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在位置2i+1上，父亲则在i/2上（小于i/2的最小整数）。

    堆序性为：使操作被快速执行的性质称为堆序性。在一个堆中，对于每个节点x，x的父节点中的关键字小于等于x中的关键字，除根节点外（根节点没有父节点）。

优先队列的声明：

struct heapStruct; typedef struct heapStruct* priorityQueue; struct heapStruct { int capacity; int size; int *elements; }; priorityQueue initialize(int maxElements); int isFull(priorityQueue h); void insert(int x, priorityQueue h); int isEmpty(priorityQueue h); int deleteMin(priorityQueue h); 初始化：

priorityQueue initialize(int maxElements) { priorityQueue h; h = (struct heapStruct*)malloc(sizeof(struct heapStruct)); if (h == NULL) cout << "Out of space!" << endl; h->elements = (int *)malloc(sizeof(int)*(maxElements + 1)); if (h->elements == NULL) cout << "Out of space!" << endl; h->capacity = maxElements; h->size = 0; h->elements[0] = INT_MIN; return h; } 插入（上滤（percolate up））： int isFull(priorityQueue h) { if (h->size == h->capacity) return 1; else return 0; } void insert(int x, priorityQueue h) { int i; if (isFull(h)) { cout << "Queue is full!" << endl; return; } for (i = ++h->size; h->elements[i / 2] > x; i = i / 2) h->elements[i] = h->elements[i / 2]; h->elements[i] = x; } 删除（下滤（percolate down））： int isEmpty(priorityQueue h) { if (h->size == 0) return 1; else return 0; } int deleteMin(priorityQueue h) { int i, child; int minElement, lastElement; if (isEmpty(h)) { cout << "Queue is empty!" << endl; return h->elements[0]; } minElement = h->elements[1]; lastElement = h->elements[h->size--]; for (i = 1; i * 2 < h->size; i = child) { child = i * 2; if (child != h->size&&h->elements[child + 1] < h->elements[child]) child++; if (lastElement>h->elements[child]) h->elements[i] = h->elements[child]; else break; } h->elements[i] = lastElement; return minElement; }