优先队列与栈

问题描述
假设某医生看病人的顺序是由病人的病情严重程度来决定。护士按照所有病人来医院的时间顺序给病人编号ID，依次为1，2，3，…，n；并且根据病人的病情严重程度设置Priority值，病越重，Priority的值越小。当医生开始工作时，护士根据病人的Priority值，由小到大依次安排病人看病。试为护士编写程序安排病人看病的先后次序。

测试数据
输入
1 15
2 3
3 5
4 20
5 10
－1 －1
输出
2
3
5
1
4

解决方案：

建最小值堆

  1 #include<iostream>
  2 #include<stdlib.h>
  3 #define maxSize 100
  4 
  5 using namespace std;
  6 typedef struct
  7 {
  8     int id;
  9     int priority;
 10 }information;
 11 information info[maxSize];
 12 
 13 void swapInfo(information *a,information *b)
 14 {
 15     information tem=*a;
 16     *a=*b;
 17     *b=tem;
 18 }
 19 void init(information info[],int a[],int b[],int total)
 20 {
 21     int i=0;
 22     while(i<total)
 23     {
 24         info[i].id=a[i];
 25         info[i].priority=b[i];
 26         i++;
 27     }
 28 }
 29 void adjustInfo(information info[],int cur,int end)
 30 {
 31     int l=2*cur+1;
 32     int r=2*cur+2;
 33     int largest;
 34     if(l<end&&info[cur].priority<info[l].priority)
 35         largest=l;
 36     else
 37         largest=cur;
 38     if(r<end&&info[largest].priority<info[r].priority)
 39         largest=r;
 40     if(largest!=cur)
 41     {
 42         swapInfo(&info[cur],&info[largest]);
 43 
 44         adjustInfo(info,largest,end);
 45     }
 46 
 47 }
 48 int top(information info[])
 49 {
 50     return info[0].priority;
 51 }
 52 void build(information info[],int total)
 53 {
 54     for(int i=(total-2)/2;i>=0;i--)
 55     {
 56         adjustInfo(info,i,total);
 57     }
 58 }
 59 
 60 void sortInfo(information info[],int total)
 61 {
 62     build(info,total);
 63     for(int i=total-1;i>=0;i--)
 64     {
 65         swapInfo(&info[i],&info[0]);
 66         adjustInfo(info,0,i);
 67     }
 68 }
 69 void print(information info[],int total)
 70 {
 71     for(int i=0;i<total;i++)
 72     {
 73         cout<<info[i].id<<"     "<<info[i].priority<<endl;
 74     }
 75 }
 76 bool isempty(information info)
 77 {
 78     if(total==0)
 79         return 1;
 80     else
 81         return false;
 82 }
 83 int total;
 84 int main()
 85 {
 86     cout<<"input the information of patient:"<<endl;
 87     int i=0,a[maxSize],b[maxSize];
 88 
 89     while(1)
 90     {
 91         cin>>a[i]>>b[i];
 92         if((a[i]<=0)&&(b[i]<=0))
 93             break;
 94         i++;
 95     }
 96     total=i;
 97     init(info,a,b,total);
 98     cout<<"top"<<top(info)<<endl;
 99     sortInfo(info,total);
100     print(info,total);
101     cout<<"3Q~"<<endl;
102     return 0;
103 
104 }

View Code

数组

  1 #include<iostream>
  2 #include<stdlib.h>
  3 #define maxSize 100
  4 
  5 using namespace std;
  6 typedef struct
  7 {
  8     int id;
  9     int priority;
 10 }information;
 11 information info[maxSize];
 12 
 13 void swapInfo(information *a,information *b)
 14 {
 15     information tem=*a;
 16     *a=*b;
 17     *b=tem;
 18 }
 19 void init(information info[],int a[],int b[],int total)
 20 {
 21     int i=0;
 22     while(i<total)
 23     {
 24         info[i].id=a[i];
 25         info[i].priority=b[i];
 26         i++;
 27     }
 28 }
 29 void adjustInfo(information info[],int cur,int end)
 30 {
 31     int l=2*cur+1;
 32     int r=2*cur+2;
 33     int largest;
 34     if(l<end&&info[cur].priority<info[l].priority)
 35         largest=l;
 36     else
 37         largest=cur;
 38     if(r<end&&info[largest].priority<info[r].priority)
 39         largest=r;
 40     if(largest!=cur)
 41     {
 42         swapInfo(&info[cur],&info[largest]);
 43 
 44         adjustInfo(info,largest,end);
 45     }
 46 
 47 }
 48 int top(information info[])
 49 {
 50     return info[0].priority;
 51 }
 52 void build(information info[],int total)
 53 {
 54     for(int i=(total-2)/2;i>=0;i--)
 55     {
 56         adjustInfo(info,i,total);
 57     }
 58 }
 59 
 60 void sortInfo(information info[],int total)
 61 {
 62     build(info,total);
 63     for(int i=total-1;i>=0;i--)
 64     {
 65         swapInfo(&info[i],&info[0]);
 66         adjustInfo(info,0,i);
 67     }
 68 }
 69 void print(information info[],int total)
 70 {
 71     for(int i=0;i<total;i++)
 72     {
 73         cout<<info[i].id<<"     "<<info[i].priority<<endl;
 74     }
 75 }
 76 bool isempty(information info)
 77 {
 78     if(total==0)
 79         return 1;
 80     else
 81         return false;
 82 }
 83 int total;
 84 int main()
 85 {
 86     cout<<"input the information of patient:"<<endl;
 87     int i=0,a[maxSize],b[maxSize];
 88 
 89     while(1)
 90     {
 91         cin>>a[i]>>b[i];
 92         if((a[i]<=0)&&(b[i]<=0))
 93             break;
 94         i++;
 95     }
 96     total=i;
 97     init(info,a,b,total);
 98     cout<<"top"<<top(info)<<endl;
 99     sortInfo(info,total);
100     print(info,total);
101     cout<<"3Q~"<<endl;
102     return 0;
103 
104 }

View Code