next up previous contents
Next: Tuning the cache behavior Up: Dynamic Heaps. A flexible Previous: The data structure

Performance of the dynamic heap

Considering that the only difference between an implicit heap and the dynamic heap structure is in the address calculation, the performance of the two should be expected to be comparable. If analysed in detail, we se that accessing an element in an implicit heap is a simple array access, which translates into an integer multiplication (or a shift) and an addition, while the same address calculation in a dynamic heap takes one array access (a shift and an addition) to get the level pointer plus another array access to get the element. During siftdown this extra cost can be divided with two, because siblings are always accessed together.

   figure146
Figure 4.2: Speed of dynamic heap relative to implicit heap

As is seen in figure 4.2 the intuition about the extra cost of the dynamic data structure is valid. The plot shows that the relative speed of the dynamic heap is within 20% of the implicit heap, even though the dynamic heapsort must carry the extra overhead of not being an inplace sort.



Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999