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

桃扇骨 2023-07-12 05:05 27阅读 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 }