如何实现一个简单的优先队列实例？

本文共计1037个文字，预计阅读时间需要5分钟。

cC++实现优先队列的简单示例 + 优先队列类模型实现：BuildMaxHeap.h头文件内容：c#ifndef BUILD_MAX_HEAP_H#define BUILD_MAX_HEAP_H

#include

templateclass MaxHeap {private: std::vector heap;

void heapifyUp(int index) { while (index > 0 && heap[parent(index)]

void heapifyDown(int index) { int largest=index; int left=leftChild(index); int right=rightChild(index);

if (left heap[largest]) { largest=left; }

if (right heap[largest]) { largest=right; }

if (largest !=index) { std::swap(heap[index], heap[largest]); heapifyDown(largest); } }

int parent(int index) { return (index - 1) / 2; } int leftChild(int index) { return 2 * index + 1; } int rightChild(int index) { return 2 * index + 2; }

public: void insert(const T& value) { heap.push_back(value); heapifyUp(heap.size() - 1); }

T extractMax() { if (heap.size()==0) { throw std::runtime_error(Heap is empty); }

T maxElement=heap[0]; heap[0]=heap.back(); heap.pop_back(); heapifyDown(0);

return maxElement; }

bool isEmpty() const { return heap.empty(); }};

#endif // BUILD_MAX_HEAP_H

C++ 实现优先队列的简单实例

优先队列类模版实现：

BuildMaxHeap.h头文件：

#include<iostream> using namespace std; #define Left(i) i*2+1 #define Right(i) i*2+2 #define Parent(i) (i-1)/2 void Max_Heapify(int a[],int length,int i) { int left,right; left=Left(i); right=Right(i); int num=i; if(left<length&&a[left]>a[i]) { num=left; } //此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确 if(right<length&&a[right]>a[num]) { num=right; } if(num!=i) { int temp; temp=a[i]; a[i]=a[num]; a[num]=temp; Max_Heapify(a,length,num); } } //此处添加利用循环方式代替递归Max_Heapify的函数，该函数可以替代Max_Heapify //在某些情况下能取得更好 的效果 void Max_Heapify1(int a[],int length,int i) { int left,right,num=i,largest=i; left=Left(i); right=Right(i); while(1) { if(a[left]>a[num]&&left<length) { largest=left; } //此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确 if(a[right]>a[largest]&&right<length) { largest=right; } if(num!=largest) { int temp; temp=a[num]; a[num]=a[largest]; a[largest]=temp; num=largest; left=Left(num); right=Right(num); } else { break; } } } void Build_Max_Heap(int a[],int length ) { int i; for(i=(length-1)/2;i>=0;i--) { Max_Heapify1(a,length,i); } } void Heap_Sort(int a[],int length) { Build_Max_Heap(a,length); int i; int temp; for(i=length-1;i>=1;i--) { temp=a[i]; a[i]=a[0]; a[0]=temp; length-=1; Max_Heapify1(a,length,0); } }

PriorQUeue.h

#include<iostream> #include "BuileMaxHeap.h" using namespace std; #define MAX 100 template <typename type>class PriorQueue { private: int length; type a[MAX]; public: PriorQueue () { int i; length=0; for(i=0;i<MAX;i++) { a[i]=0; } } ~PriorQueue() { } void BuildMaxHeapQueue(); void Init(type b[],int len); type Maxnum(); bool DeleteMax(); void IncreaseKey(int i,type key); void Insert(type key); void Print(); void Sort(); }; template<typename type>void PriorQueue<type>::Init(type b[],int len) { int i; this->length=len; if(len<=0) { cout<<"Init failed !"<<endl; } for(i=0;i<len;i++) { a[i]=b[i]; } BuildMaxHeapQueue(); } template<typename type>void PriorQueue<type>::BuildMaxHeapQueue() { Build_Max_Heap(a,length); } template<typename type>type PriorQueue<type>::Maxnum() { if(length<=0) { cout<<"the queue is empty!"<<endl; return -1; } return a[0]; } template<typename type>bool PriorQueue<type>::DeleteMax() { if(length<=0) { cout<<"the queue is empty!"<<endl; return 0; } a[0]=a[length-1]; length-=1; Max_Heapify1(a,length,0); return 1; } template<typename type>void PriorQueue<type>::IncreaseKey(int i,type key) { int num=i; if(key<a[num]) { cout<<"key is error!"<<endl; return ; } a[num]=key; while(num>0&&a[Parent(num)]<a[num]) { type temp; temp=a[num]; a[num]=a[Parent(num)]; a[Parent(num)]=temp; num=Parent(num); } } template<typename type>void PriorQueue<type>::Insert(type key) { if(length>=MAX) { cout<<"the queue is full can't add more!"<<endl; return ; } length+=1; a[length-1]=key; IncreaseKey(length-1,key); } template<typename type>void PriorQueue<type>::Print() { int i; for(i=0;i<length;i++) { cout<<a[i]<<" "; } cout<<endl; } template<typename type>void PriorQueue<type>::Sort() { Heap_Sort(a,length); }

main.cpp

#include"PriorQueue.h" #include<iostream> using namespace std; int main() { PriorQueue<int> node; int b[10]={4,1,3,2,16,9,10,14,8,7}; node.Init(b,10); int i; node.Print(); cout<<endl; cout<<node.Maxnum()<<endl; node.DeleteMax(); node.Print(); node.Insert(232); node.Sort(); node.Print(); return 0; }

以上就是数据结构优先队列的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！