Subject: Re: Callouts
To: None <>
From: Charles M. Hannum <>
List: tech-kern
Date: 03/27/1999 08:33:11
> As in "heapsort"?

No, this is just a heap, not a heapsort.  Heapsort implies that we're
creating a linear ordered list.  That's not actually very useful for
our purposes.  We just need to know what the earliest (next) event is.

> [question about heaps]

This wasn't really supposed to be a lesson in data structures, but...

It's actually quite easy to add levels to a heap dynamically.
Remember that a heap looks like:

level 0     A
level 1     B   C
level 2     C E F G
level 3     HIJKLMNO

If you're keeping the heap in a linear array, you can number the
elements from 1, starting with A, and ending with O being 15.  You
find the `children' of a given parent node by calculating parent*2 and
parent*2+1.  (If your array is 0-based, you'd use parent*2+1 and

A modification to this is to keep separate pointers to an array of
elements for each level.  Assuming your arrays are 0-based, if your
parent in heap[level][index], the children are heap[level+1][index*2]
and heap[level+1][index*2+1].

In pseudocode:

  heap[level] = malloc(2^level * elementsize)
  1stborn(heap[level][index]) = heap[level+1][index*2]
  2ndborn(heap[level][index]) = heap[level+1][index*2+1]

With this arrangement, you can multiply the heap size by ~2, or divide
it by ~2, simply by allocating or deallocating a chunk of memory.

(If you've never seen this modification before, I'm not surprised.  I
discovered it independently.  Note that in practice you'd probably
allocate the first few levels in one chunk, to avoid fragmentation and
useless startup overhead.)