Natsumeのblog


这里仅有忧伤

C语言实现优先队列

  • 2021-12-04
  • 作者 NatsumeNeko
  • ~4.42K 字

起源

先吐槽一下我的c语言老师，虽说快期末了，但是一下放40道算法题是要怎样啊，而且还是挺有难度的(包括但不限于搜索，贪心，动态规划，以及接下来要讲的优先队列)。
然后呢，在我狂暴刷题的时候遇到了这么一道题：


先看题目标签，STL！！！，让我们用c语言写STL的题是不是有点过分！！！况且我们只是刚刚入门。
再看题目，要得到最小总费用，明显，即每步都合并最小的两堆。结合STL标签的提示，只要用优先队列不断pop最小的两堆合成后push，循环往复直到队列元素只剩下1个为止，时间复杂度为O(NlogN)。C++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int>>q;\\小顶堆
    int n,t;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        q.push(t); 
    }
    int res=0,temp=0;
    while(q.size()>1)\\当元素为1时结束
    {
        temp=0;
        temp+=q.top();
        q.pop();
        temp+=q.top();\\弹出最小的两个元素
        q.pop();
        q.push(temp);\\加入新元素
        res+=temp;
    }
    cout << res << endl;
    return 0;\\华丽结束
}

是不是非常简单
然而无奈老师设置了只能用c语言提交，所以要么自己动手实现优先队列的操作，要么另寻他法。但是本蒟蒻又找不到别的好办法，所以决定想办法动手实现优先队列。
而后上网冲浪得知，优先队列的实现利用了二叉堆。那么赶快动手实现叭

解决

先说二叉堆是什么：

这张图应该足以解释了也就是父节点总是不小于(或不大于)子节点的二叉树，很好理解叭。
那么如何在数组中表示这些元素的位置呢？其实很简单，假设根节点位于0，则父节点为n时，左子节点为2*n+1，右子节点为2*n+2(即为左子节点+1)。而已知子节点为n时，其父节点为(n-1)/2。
接下来，就是如何进行push和pop操作了。(以下为小顶堆为例)
先说push操作，假设要在二叉堆heap中插入一个元素x，只需将其先放在heap的末尾，然后不断和其父节点比较，如果小于父节点，则交换二者、继续比较，否则停止。
代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void heap_push(int x)
{
    heap[++front]=x;//front代表末尾的位置
    int now=front;
    while (now>0)//比较到根节点为止
    {
        if (heap[now]<heap[(now-1)/2])
        {
            swap(heap+now,heap+(now-1)/2);
            now=(now-1)/2;    
        }
        else
        {
            return;
        }
    }
}

再说pop操作，pop即是取出heap中的第一个元素，亦即根节点。pop出一个值很简单，重点在于如何找出替代根节点的值。为了不破坏整体结构，我们先选择最后一个元素取代根节点的值，然后不断和子节点中的较小值比较，如果其大于该较小值，则交换二者，否则停止。
代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int heap_pop()
{
    int pop=heap[0];\\pop代表弹出的值
    heap[0]=heap[front--];
    int now=0;
    while (now<front)\\到末尾位置时停止
    {
        int l=now*2+1;\\左子节点
        if (l<=front)
        {
            if (l+1<=front)\\注意右子节点可能不存在
            {
                int r=l+1;
                if (heap[l]>heap[r])
                {
                    l=r;
                }
            }
            if (heap[now]>heap[l])
            {
                swap(heap+now,heap+l);
                now=l;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
    return pop;
}

实现了这两个操作，再解决这题就很简单惹~~~
完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int cmp(const void *a,const void *b)\\qsort模板比较函数
{
    return (*(int*)a-*(int*)b);
}
void swap(int *a,int *b)\\交换元素函数
{
    int x=*a;
    *a=*b;
    *b=x;
}
int heap[100005];\\优先队列
int n,front;
void heap_push(int a)\\push函数
{
    heap[++front]=a;
    int now=front;
    while (now>0)
    {
        if (heap[now]<heap[(now-1)/2])
        {
            swap(heap+now,heap+(now-1)/2);
            now=(now-1)/2;    
        }
        else
        {
            return;
        }
    }
}
int heap_pop()\\pop函数
{
    int pop=heap[0];
    heap[0]=heap[front--];
    int now=0;
    while (now<front)
    {
        int l=now*2+1;
        if (l<=front)
        {
            if (l+1<=front)
            {
                int r=l+1;
                if (heap[l]>heap[r])
                {
                    l=r;
                }
            }
            if (heap[now]>heap[l])
            {
                swap(heap+now,heap+l);
                now=l;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
    return pop;
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&heap[i]);
    }
    qsort(heap,n,sizeof(heap[0]),cmp);\\先排序，方便后续操作
    int res=0;
    front=n-1;
    while (front>0)\\元素个数为1时停止
    {
        int a1=heap_pop();
        int b1=heap_pop();
        res+=a1+b1;
        heap_push(a1+b1);   
    }
    printf("%d\n",res);
    return 0;\\华丽结束
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , ,
最后编辑：2021-12-05