Skip to Main Content
Mastering Algorithms with C
book

Mastering Algorithms with C

by Kyle Loudon
August 1999
Intermediate to advanced content levelIntermediate to advanced
560 pages
18h 57m
English
O'Reilly Media, Inc.
Content preview from 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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Luciano Manelli
Head First C

Head First C

David Griffiths, Dawn Griffiths

Publisher Resources

ISBN: 1565924533Supplemental ContentErrata Page