1 /* Copyright (C) 2007 Keith Rarick and Philotic Inc.
2 * Copyright 2011 Keith Rarick
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
25 set(Heap
*h
, int k
, void *x
)
33 swap(Heap
*h
, int a
, int b
)
38 set(h
, a
, h
->data
[b
]);
44 cmp(Heap
*h
, int a
, int b
)
46 return h
->cmp(h
->data
[a
], h
->data
[b
]);
51 siftdown(Heap
*h
, int k
)
54 int p
= (k
-1) / 2; /* parent */
56 if (k
== 0 || cmp(h
, k
, p
) >= 0) {
67 siftup(Heap
*h
, int k
)
72 l
= k
*2 + 1; /* left child */
73 r
= k
*2 + 2; /* right child */
75 /* find the smallest of the three */
77 if (l
< h
->len
&& cmp(h
, l
, s
) < 0) s
= l
;
78 if (r
< h
->len
&& cmp(h
, r
, s
) < 0) s
= r
;
81 return; /* satisfies the heap property */
91 heapinsert(Heap
*h
, void *x
)
95 if (h
->len
== h
->cap
) {
97 int ncap
= (h
->len
+1) * 2; /* allocate twice what we need */
99 ndata
= malloc(sizeof(void*) * ncap
);
104 memcpy(ndata
, h
->data
, sizeof(void*)*h
->len
);
119 heapremove(Heap
*h
, int k
)
129 set(h
, k
, h
->data
[h
->len
]);