forked from bcribas/benchmark-ordenacao
-
Notifications
You must be signed in to change notification settings - Fork 0
/
priority-queue.c
64 lines (57 loc) · 1.09 KB
/
priority-queue.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
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
/*
* Copyright(C) 2020, Bruno César Ribas <bruno.ribas@unb.br>
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of version 2.1 of the GNU Lesser General Public License
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it would be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
*/
#include <stdlib.h>
#include "ordenacaomacros.h"
#include "priority-queue.h"
static Item *pq;
static int N;
void PQinit(int maxN)
{
pq=malloc(sizeof(Item)*maxN);
N=0;
}
int PQempty()
{
return N==0;
}
void PQinsert(Item v)
{
pq[++N]=v;
fixUp(pq,N);
}
Item PQdelmax()
{
exch(pq[1],pq[N]);
fixDown(pq,1,N-1);
return pq[N--];
}
void fixUp(Item *pq, int k)
{
while(k>1 && less(pq[k/2],pq[k]))
{
exch(pq[k],pq[k/2]);
k=k/2;
}
}
void fixDown(Item *pq, int k, int N)
{
int j;
while(2*k <= N)
{
j=2*k;
if(j<N && less(pq[j],pq[j+1])) j++;
if(!less(pq[k],pq[j])) break;
exch(pq[k],pq[j]);
k=j;
}
}