priority_queue优先队列.doc

#includestdio.h #includeiostream #includealgorithm #includequeue #includefunctional #include time.h//用于做种子 #include stdlib.h using namespace std; struct mytype //自定义的一个类，要在类中重载小于符号 { int value; int index; bool operator(const mytype b) { return valueb.value; } }; struct cmp{ //还得再写一个类，用于实现优先级的比较函数，就是重载小括号。 bool operator ()(const mytype a,const mytype b){ return a.valueb.value; } }; int ForInstance(priority_queuemytype,vectormytype,cmp q)//重构一个priority_queue的构造方法， { srand(time(NULL));//使用这个就可以每次不同 for(int i=0;i10;i++) { int k=rand(); mytype t; t.value=k; t.index=i; q.push(t); coutindex=i value= kendl; } coutendl; while(!q.empty()) { mytype t=q.top(); q.pop(); coutindex=t.index value= t.valueendl; } return 0; } int GetKey(priority_queuemytype,vectormytype,cmp q) { mytype t; int n; cout请输入要数据个数endl; cinn; int k; cout请输入n个数据endl; for(int i=0;in;i++) { cink; t.value=k; t.index=i; q.push(t); cout value= kendl; } return 1; } int main() { priority_queuemytype,vectormytype,cmpq;//创建优先队列，采用重构了一个比较的方法，优先队列为小顶堆 int choose;//控制选择 mytype t; while(choose)//菜单选择 { cout1.举例输入输出endl; cout2.初始化输入数据endl; cout3.插入数据endl; cout4.查找优先值最大的数据endl; cout5.删除优先值最大的数据endl; cout6.输出数据endl; cout0.退出endl; cinchoose; switch(choose) { case 1: ForInstance(q);//举例说明 cout例子如上endl; break; case 2: if(GetKey(q))//2.初始化输入数据 cout成功输入数据endl; else return 0; break; case 3:cint.value;//插入数据 q.push(t); cout成功插入数据endl; break; case 4: t=q.top();//4.查找优先值最大的数据 cout最小value= t.valueendl; break; case 5: t=q.top();//5.删除优先值最大的数据 cout最小value= t.valueendl; q.pop(); cout成功删除最小元素endl;break; case 6://6.输出优先值最大的数据 while(!q.empty()) { mytype t=q.top(); q.pop(); cout value= t.valueendl; } break; case 0:return 0; } } return 0; }数据结构： priority_queue mytype,vectormytype,cmpq;创建优先队列，采用重构了一个比较的方法，优先队列为小顶堆，类型为mytype struct mytype //自定义的一个结构体，要在结构体中重载小于符号 {int value;int index;} 算法实现： struct cmp{}用于实