Mastering Algorithms With C - Kyle Loudon [111]
if ((data = (Parcel *)malloc(sizeof(Parcel))) == NULL)
return -1;
/*****************************************************************************
* *
* Insert the parcel into the priority queue. *
* *
*****************************************************************************/
memcpy(data, parcel, sizeof(Parcel));
if (pqueue_insert(parcels, data) != 0)
return -1;
return 0;
}
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 heap_ parent, heap_left, and heap_right quickly determine the position of a node's parent, left child, and right child in a tree represented in an array. The reason these macros are not defined in heap.h is that they are not a part of the public heap interface. That is, a developer using a heap should not be permitted to traverse a heap's nodes indiscriminately. Instead, access to the heap is restricted to those operations defined by the interface published in heap.h.
Q: Recall that left-balanced binary trees are particularly well-suited to arrays. Why is this not true of all binary trees?
A: Left-balanced binary trees are particularly well-suited to arrays because no nodes go unused between positions and n - 1, where n is the number of nodes in the tree. Array representations of binary trees that are not left-balanced, on the other hand, contain gaps of unused nodes. For example, suppose a binary tree of 10 levels is completely full through 9 levels, but in the tenth level only 1 node resides at the far right. In contiguous storage, the node at the far right of the tenth level resides at position 210 - 2 = 1022 (in a zero-indexed array). The node at the far right of the ninth level resides at position 29 - 2 = 510. This results in (1022 - 510) - 1= 511 empty positions out of the total 1023 positions required to represent the tree. Thus, only 50% of the array is being used.
Q: Suppose we are using a priority queue to prioritize the order in which tasks are scheduled by an application. If the system continually processes a large number of high-priority tasks, what problems might the system exhibit? How can we correct this?
A: When high-priority elements are continually being inserted into a priority queue, lower-priority elements may never rise to the top. In a task scheduler, for example, the lower-priority tasks are said to be experiencing starvation . To manage this, typically a system employs some mechanism to increase a task's priority gradually as its time in the queue grows. Thus, even in a busy system flooded by high-priority tasks, a low-priority task eventually will obtain a high enough priority to rise to the top. Operating systems