Instead of allocating the heap in one contiguous memory area, memory for each level is allocated separately, and an array with one pointer to each data area is set up. Now the heap can be extended by allocating memory for the new level and pointing the corresponding level pointer to the newly allocated memory area.
The level pointers can be statically allocated. 64 pointers are enough for any application.
In order to avoid spending excessive time in memory allocation and deallocation the following allocation policy is adopted.
With this policy the average utilisation of allocated memory is 75% in a growing heap and 38% in a shrinking heap. Also the worst case memory utilisation is seen to be 25% if we ignore the situation with a very small heap (eg. one element).
The dynamic heap data structure is shown in figure 4.1.
In order to implement the siftup and siftdown procedures effectively, we need to know how to find the parent of an element and the childrens of an element. This is how it is done:
Assuming that the elements on each level are numbered beginning from 0, the childrens of element i on level l can be found at level l+1 in positions 2i and 2i+1, and the parent of the element is at level l-1 in position i/2 (integer division).
Figure 4.1: Data structure of dynamic heap