8 set(Heap
*h
, int k
, void *x
)
16 swap(Heap
*h
, int a
, int b
)
21 set(h
, a
, h
->data
[b
]);
27 less(Heap
*h
, int a
, int b
)
29 return h
->less(h
->data
[a
], h
->data
[b
]);
34 siftdown(Heap
*h
, int k
)
37 int p
= (k
-1) / 2; /* parent */
39 if (k
== 0 || less(h
, p
, k
)) {
50 siftup(Heap
*h
, int k
)
55 l
= k
*2 + 1; /* left child */
56 r
= k
*2 + 2; /* right child */
58 /* find the smallest of the three */
60 if (l
< h
->len
&& less(h
, l
, s
)) s
= l
;
61 if (r
< h
->len
&& less(h
, r
, s
)) s
= r
;
64 return; /* satisfies the heap property */
73 // Heapinsert inserts x into heap h according to h->less.
74 // It returns 1 on success, otherwise 0.
76 heapinsert(Heap
*h
, void *x
)
80 if (h
->len
== h
->cap
) {
82 int ncap
= (h
->len
+1) * 2; /* allocate twice what we need */
84 ndata
= malloc(sizeof(void*) * ncap
);
89 memcpy(ndata
, h
->data
, sizeof(void*)*h
->len
);
104 heapremove(Heap
*h
, int k
)
114 set(h
, k
, h
->data
[h
->len
]);