优先队列（非模板函数，是int）

发现了一个可能是书里的错误，在swim函数中while检测的条件

void priorityQueue::Swim(size_t t) { inArr[0]=inArr[t]; while (inArr[t/2]<inArr[t])//这里我认为不对,我认为因是inArr[0] { inArr[t]=inArr[t/2]; t/=2; } inArr[t]=inArr[0]; }

头文件

#include <vector> #ifndef LUPRIORITY_QUEUE #define LUPRIORITY_QUEUE class priorityQueue { public: int Top() const; void Pop(); void Push(int t); bool IsEmpty() const; size_t Size() const; priorityQueue();//将inArr初始化，存放一个元素 private: void Swim(size_t t); void Sink(); public: std::vector<int> inArr; }; #endif 定义文件，因为没有用模板函数，所以定义可以分开写。模板函数，定义要和声明卸载一起。

#include "LUpriority_queue.h" priorityQueue::priorityQueue():inArr(1) { } bool priorityQueue::IsEmpty() const { return inArr.size()==1;//注意一直保存着0节点 } int priorityQueue::Top() const { return inArr[1]; } void priorityQueue::Push(int t) { inArr.push_back(t); Swim(inArr.size()-1); } void priorityQueue::Pop() { inArr[1]=inArr[inArr.size()-1]; inArr.pop_back(); Sink(); } void priorityQueue::Swim(size_t t) { inArr[0]=inArr[t]; while (inArr[t/2]<inArr[0]) { inArr[t]=inArr[t/2]; t/=2; } inArr[t]=inArr[0]; } void priorityQueue::Sink() { int i=1; int rightChild=i*2+1; inArr[0]=inArr[i]; while (rightChild<inArr.size()) { int max=i; if (inArr[max]<inArr[rightChild]) { max=rightChild; } //max的两种情况，右孩子比节点小，或者此时max已经是右孩子 //但是右孩子比左孩子小 if (inArr[max]<inArr[rightChild-1]) { max=rightChild-1; } <pre name="code" class="cpp"> //注意，能使用else{break;}，原因是else紧跟着最近的if在一起， //如果上一条不执行，一定会执行这句else   if(max==i){break;}inArr[i]=inArr[max];rightChild=max*2+1;i=max;}if (rightChild==inArr.size()){if (inArr[i]<inArr[rightChild-1]){inArr[i]=inArr[rightChild-1];i=rightChild-1;}}inArr[i]=inArr[0];} 测试代码

<pre name="code" class="cpp">#include "LUpriority_queue.h" #include <iostream> int main() { using std::cin; using std::cout; using std::endl; priorityQueue t; t.Push(9); for (int i=0;i<t.inArr.size();i++) { cout<<t.inArr[i]; } cout<<endl; t.Push(4); for (int i=0;i<t.inArr.size();i++) { cout<<t.inArr[i]; }cout<<endl; t.Push(8); for (int i=0;i<t.inArr.size();i++) { cout<<t.inArr[i]; }cout<<endl; t.Push(2); for (int i=0;i<t.inArr.size();i++) { cout<<t.inArr[i]; }cout<<endl; t.Push(7); for (int i=0;i<t.inArr.size();i++) { cout<<t.inArr[i]; } cout<<endl; cout<<t.Top(); t.Pop(); cout<<t.Top(); t.Pop(); cout<<t.Top(); t.Pop(); cout<<t.Top(); t.Pop(); cout<<t.Top(); system("pause"); return 0; }