C语言实现优先队列


起源

先吐槽一下我的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
接下来,就是如何进行pushpop操作了。(以下为小顶堆为例)
先说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;\\华丽结束
}