优先级队列-堆的简单实现-蒲公英云

优先级队列-堆的简单实现

桃扇骨 2023-07-12 05:05 134阅读 0赞

1 #include <cstdio>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 const int MAX_N = 1000;
 7 
 8 // 用数组来实现二叉树
 9 // 左儿子编号=自己*2 + 1
10 // 右儿子编号=自己*2 + 1
11 int heap[MAX_N],sz=0;
12 
13 // 实现最小堆
14 void push(int x)
15 {
16     // 取最后一个节点的编号，并递增。
17     int i=sz++;
18     // 循环更改所有颠倒序列
19     while(i>0)
20     {
21         int p=(i-1)/2;
22         // 无颠倒序列，退出循环
23         if(heap[p]<=x)
24         {
25             break;
26         }
27         else
28         {
29             heap[i]=heap[p];
30             i=p;
31         }
32     }
33     // 填入新数
34     heap[i]=x;
35 }
36 
37 // 返回最小值（堆顶），然后在堆顶放置堆中最后一个元素
38 // 向下更新，直到有序
39 int pop()
40 {
41     int ret=heap[0];
42     // 记录要提到根节点的数
43     int x=heap[--sz];
44     int i=0;
45     while(2*i+1 < sz)
46     {
47        int a=2*i+1,b=2*i+2;
48        // 如果存在右儿子，且右儿子的值比做儿子小，则记左右儿子中较小者编号a为右儿子的编号
49        if(b<sz && heap[a]>heap[b])
50        {
51            a=b;
52        }
53        // 无逆序，退出循环
54        if(heap[a]>=x)
55        {
56            break;
57        }
58        // 否则将较小数前提,继续向下寻找
59        heap[i]=heap[a];
60        i=a;
61     }
62     // 最后将x写入适当的位置
63     heap[i]=x;
64 
65     return ret;
66 }
67 
68 
69 int main()
70 {
71     push(1);
72     push(5);
73     push(4);
74 
75     cout<<pop()<<endl;
76     push(2);
77     push(7);
78     cout<<pop()<<endl;
79     cout<<pop()<<endl;
80     push(9);
81     for(int i=0;i<3;++i)
82     {
83         cout<<pop()<<endl;
84     }
85     return 0;
86 }