heap.c

   1 #include <stdint.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "dat.h"
   5
   6
   7 static void
   8 set(Heap *h, int k, void *x)
   9 {
  10     h->data[k] = x;
  11     h->rec(x, k);
  12 }
  13
  14
  15 static void
  16 swap(Heap *h, int a, int b)
  17 {
  18     void *tmp;
  19
  20     tmp = h->data[a];
  21     set(h, a, h->data[b]);
  22     set(h, b, tmp);
  23 }
  24
  25
  26 static int
  27 less(Heap *h, int a, int b)
  28 {
  29     return h->less(h->data[a], h->data[b]);
  30 }
  31
  32
  33 static void
  34 siftdown(Heap *h, int k)
  35 {
  36     for (;;) {
  37         int p = (k-1) / 2; /* parent */
  38
  39         if (k == 0 || less(h, p, k)) {
  40             return;
  41         }
  42
  43         swap(h, k, p);
  44         k = p;
  45     }
  46 }
  47
  48
  49 static void
  50 siftup(Heap *h, int k)
  51 {
  52     for (;;) {
  53         int l, r, s;
  54
  55         l = k*2 + 1; /* left child */
  56         r = k*2 + 2; /* right child */
  57
  58         /* find the smallest of the three */
  59         s = k;
  60         if (l < h->len && less(h, l, s)) s = l;
  61         if (r < h->len && less(h, r, s)) s = r;
  62
  63         if (s == k) {
  64             return; /* satisfies the heap property */
  65         }
  66
  67         swap(h, k, s);
  68         k = s;
  69     }
  70 }
  71
  72
  73 // Heapinsert inserts x into heap h according to h->less.
  74 // It returns 1 on success, otherwise 0.
  75 int
  76 heapinsert(Heap *h, void *x)
  77 {
  78     int k;
  79
  80     if (h->len == h->cap) {
  81         void **ndata;
  82         int ncap = (h->len+1) * 2; /* allocate twice what we need */
  83
  84         ndata = malloc(sizeof(void*) * ncap);
  85         if (!ndata) {
  86             return 0;
  87         }
  88
  89         memcpy(ndata, h->data, sizeof(void*)*h->len);
  90         free(h->data);
  91         h->data = ndata;
  92         h->cap = ncap;
  93     }
  94
  95     k = h->len;
  96     h->len++;
  97     set(h, k, x);
  98     siftdown(h, k);
  99     return 1;
 100 }
 101
 102
 103 void *
 104 heapremove(Heap *h, int k)
 105 {
 106     void *x;
 107
 108     if (k >= h->len) {
 109         return 0;
 110     }
 111
 112     x = h->data[k];
 113     h->len--;
 114     set(h, k, h->data[h->len]);
 115     siftdown(h, k);
 116     siftup(h, k);
 117     h->rec(x, -1);
 118     return x;
 119 }