优先队列(二叉堆)-C实现.doc

优先队列包括二叉堆、d-堆、左式堆、斜堆、二项队列等1、二叉堆 堆是一棵被完全填满的二叉树，有可能例外的是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。 堆序的性质：在一个堆中，对于每一个节点X，X的父亲的关键字小于（或等于）X中的关键字，根节点除外（它没有父节点）。完全二叉树可以用数组实现。如果要插入的元素是新的最小值，那么它将一直被推向堆顶。这样在某一个时刻，i将是1，我们就需要另Insert函数令程序跳出while循环，这个值必须保证小于或者至少等于堆中的任何值，我们称之为标记。-#include using namespace std;class bitHeappublic:bitHeap(int n);bitHeap();int isFull(void);int isEmpty(void);void show(void);void insertInt(int x);void deleteInt(void);private:int Size;int Capacity;int *Eles;int main(void)class bitHeap H(5);H.insertInt(1);H.insertInt(23);H.insertInt(45);H.insertInt(6);H.insertInt(9);H.insertInt(19);H.show();H.deleteInt();H.show();return 0;bitHeap:bitHeap(int n)Eles = new intn+1;Eles0 = (1Capacity = n;this-Size = 0;coutcreat the Eles is okendl;bitHeap:bitHeap()delete Eles;coutdelete the Eles is ok= Capacity);int bitHeap:isEmpty(void)return (Size = 0);void bitHeap:show(void)for(int i = 1; i Size; i+)coutElesi ;coutisFull()coutThe heap is full. x; i /= 2)Elesi = Elesi/2;Elesi = x;void bitHeap:deleteInt(void)if(this-isEmpty()coutThe heap is empty.Eles(this-Size)-;int i, child;for(i = 1; 2*i Size; i = child)child = 2 * i;if(child != Size & this-Eleschild Eleschild+1)child+;if(this-Eleschild Elesi = this-Eleschild;elsebreak;this-Elesi = lastVal;-2、d-堆是二叉堆的简单推广，它恰像一个二叉堆，只是所有的节点都有d个儿子（