优先队列(二叉堆)-c实现

《优先队列(二叉堆)-c实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、优先队列包括二叉堆、d-堆、左式堆、斜堆、二项队列等1、二叉堆       堆是一棵被完全填满的二叉树，有可能例外的是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。       堆序的性质：在一个堆中，对于每一个节点X，X的父亲的关键字小于（或等于）X中的关键字，根节点除外（它没有父节点）。完全二叉树可以用数组实现。如果要插入的元素是新的最小值，那么它将一直被推向堆顶。这样在某一个时刻，i将是1，我们就需要另Insert函数令程序跳出while循环，这个值必须保证小于或者至少等于堆中的任何值，我们称之为标记。----------------------------------

2、------------------------------------------------------------------------------------#includeusingnamespacestd;classbitHeap{public:bitHeap(intn);~bitHeap();intisFull(void);intisEmpty(void);voidshow(void);voidinsertInt(intx);voiddeleteInt(void);private:intSize;intCapacity;int*Eles;};intma

3、in(void){classbitHeapH(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();return0;}bitHeap::bitHeap(intn){Eles=newint[n+1];Eles[0]=(1<<31);this->Capacity=n;this->Size=0;cout<<"creattheEles[]isok"<

4、(){delete[]Eles;cout<<"deletetheEles[]isok"<=Capacity);}intbitHeap::isEmpty(void){return(Size==0);}voidbitHeap::show(void){for(inti=1;i<=this->Size;i++)cout<Eles[i]<<"";cout<isFull()){cout<<"Theheapisf

5、ull."<x;i/=2)Eles[i]=Eles[i/2];Eles[i]=x;}voidbitHeap::deleteInt(void){if(this->isEmpty()){cout<<"Theheapisempty."<Eles[(this->Size)--];inti,child;for(i=1;2*iSize;i=child){child=2*i;if(child!=Size&&this->Eles[child]

6、his->Eles[child+1])child++;if(this->Eles[child]Eles[i]=this->Eles[child];elsebreak;}this->Eles[i]=lastVal;}---------------------------------------------------------------------------------------------------------------------2、d-堆是二叉堆的简单推广，它恰像一个二叉堆，只是所有的节点都有d个儿子（可以说二叉堆是2-堆）3、优先队列还包括

7、了左式堆、斜堆、二项队列等。     可以参考《数据结构与算法分析-C语言描述》第6章-优先队列（堆）