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
88
89
90
91
92
93
94
95
96
97
98
99
100
|
/*
* Copyright © 2005-2009 Bart Massey
* ALL RIGHTS RESERVED
* [This program is licensed under the "3-clause ('new') BSD License"]
* Please see the file COPYING in the source
* distribution of this software for license terms.
*/
/*
* heap max int priority queue
* Bart Massey 2005/03
*/
#include <assert.h>
#include <stdlib.h>
#include "heap.h"
unsigned *heap = 0;
int nheap = 0;
static int maxheap = 0;
void heap_reset(int size) {
nheap = 0;
maxheap = size;
if (heap)
free (heap);
heap = malloc(size * sizeof(*heap));
assert(heap);
}
/* push the top of heap down as needed to
restore the heap property */
static void downheap(void) {
int tmp;
int i = 0;
while(1) {
int left = (i << 1) + 1;
int right = left + 1;
if (left >= nheap)
return;
if (right >= nheap) {
if (heap[i] < heap[left]) {
tmp = heap[left];
heap[left] = heap[i];
heap[i] = tmp;
}
return;
}
if (heap[i] >= heap[left] &&
heap[i] >= heap[right])
return;
if (heap[left] > heap[right]) {
tmp = heap[left];
heap[left] = heap[i];
heap[i] = tmp;
i = left;
} else {
tmp = heap[right];
heap[right] = heap[i];
heap[i] = tmp;
i = right;
}
}
}
unsigned heap_extract_max(void) {
unsigned m;
assert(nheap > 0);
/* lift the last heap element to the top,
replacing the current top element */
m = heap[0];
heap[0] = heap[--nheap];
/* now restore the heap property */
downheap();
/* and return the former top */
return m;
}
/* lift the last value on the heap up
as needed to restore the heap property */
static void upheap(void) {
int i = nheap - 1;
assert(nheap > 0);
while(i > 0) {
int tmp;
int parent = (i - 1) >> 1;
if (heap[parent] >= heap[i])
return;
tmp = heap[parent];
heap[parent] = heap[i];
heap[i] = tmp;
i = parent;
}
}
void heap_insert(unsigned v) {
assert(nheap < maxheap);
heap[nheap++] = v;
upheap();
}
|
