Untested C heap include

heap.h

/* completely untested */

struct _heap_data
#if 0
  {
    struct _heap_cnt    cnt;
    const char          *cwd;
    ..
  }
#endif
;

struct _heap_cnt
  {
    int			count, use;
  };

struct _heap
  {
    unsigned		len, size;
    int			(*cmp)(struct _heap_data *, struct _heap_data *);
    union _heap_u
      {
	struct _heap_cnt	*cnt;	/* must be in all heap elements	*/
	struct _heap_data	*data;
      }			*data;
  };

struct _heap_data *
heap_push(struct _heap *h, struct _heap_data *data)
{
  unsigned	idx;

  /* lock? */
  if (h->len == h->size)
    {
      if ((h->size <<= 1)==0)
	h->size	= 1;
      if (h->len >= h->size)
        FATAL("heap: length overfolow");
      h->data = realloc(h->data, h->size * sizeof *h->data);
      if (!h->data)
        FATAL("out of memory");
    }

  idx	= h->len;
  h->len++;
  while (idx)
    {
      int	res;
      unsigned	prnt;

      prnt	= (idx-1) >> 1;
      res	= (*h->cmp)(h->data[prnt].data, data);
      if (0 <= res)
        {
          if (res)
	    break;
	  FATAL("heap: element to insert not unique");
        }
      /* current element is higher than parent which is higher than all lower elements.
       * So current element is higher than all elements below parent, too.
       */
      h->data[idx] = h->data[prnt];
      idx	   = prnt;
    }
  h->data[idx].data = data;
  h->data[idx].cnt->count++;
  h->data[idx].cnt->use++;
  /* unlock */
  return data;
}

/* return top element
 */
struct _heap_data *
heap_pop(struct _heap *h)
{
  struct _heap_data	*ret, *data;
  unsigned		idx, el;

  if (!h->len)
    return 0;

  /* lock? */

  h->data->cnt->use++;
  ret = h->data->data;

  data	= h->data[h->len-1].data;
  h->len--;

  idx	= 0;
  while (h->len < (el=(idx<<1)+1))
    {
      union _heap_u *ptr;

      ptr = &h->data[el];
      if (h->len > el+1 && 0 < (*h->cmp)(ptr[0].data, ptr[1].data))
        ptr++;
      if (0 <= (*h->cmp)(data, ptr->data))
        break;
      h->data[idx].data = ptr->data;
    }
  h->data[idx].data	= data;
  /* unlock */
  return ret;
}