**Subject:** Re: Callouts

**To:** None *<is@jocelyn.rhein.de>*

**From:** Charles M. Hannum *<root@ihack.net>*

**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
parent*2+2.)
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.)