Mastering Algorithms with C

Questions and Answers

Q: To build a heap from a set of data using the interface presented in this chapter, we call heap_insert once for each element in the set. Since heap_insert runs in O (lg n) time, building a heap of n nodes requires O (n lg n) time. What is an alternative to this approach that runs in O (n) time?

A: An alternative to calling heap_insert repeatedly is to start with an array of nodes that we heapify by pushing data downward just as is done in heap_insert. In this approach, we first heapify the tree whose root is at position └ n/2┘ - 1, then heapify the tree whose root is at position └ n/2┘ - 2, and continue this process until we heapify the tree rooted at position 0. This approach relies on the observation that the nodes at └ n/2┘ to n - 1 (in a zero-indexed array) are one-node heaps themselves because they are the leaf nodes. Building a heap in this way is efficient because although there are └ n/2┘ - 1 operations that run in O (lg n) time, a tighter analysis reveals that even in the worst case only half the heapifications require comparing data at more than one level. This results in an O (n) running time overall. On the other hand, when calling heap_insert repeatedly, half the heapifications could require traversing all lg n levels in the worst case. Thus, building a heap in this way runs in O (n lg n) time.

Q: Why are heap_ parent, heap_left , and heap_right defined in heap.c, whereas the other heap macro, heap_size, is defined in heap.h?

A: The macros