Heaps and Priority Queues Questions and Answers

Answer: A

The max-heap is 25,12,16,8,10,13,14.

In an array heap the children of position i are at 2i and 2i + 1. Check each parent: 25 is above 12 and 16; 12 is above 8 and 10; 16 is above 13 and 14. Every parent is at least as large as its children.

The others fail: in 25,12,16,13,10,8,14 the node 12 has child 13; in 25,14,12,13,10,8,16 the node 12 has child 16; and in 25,14,12,13,10,16,8 the node 12 again has child 16.

Answer: B

The worst case is \(\theta(\log n)\).

Extracting the minimum removes the root, moves the last element into its place, and sifts it down, swapping with the smaller child at each level. A binary heap of n elements has height \(\lfloor \log_{2} n \rfloor\), so at most about \(\log n\) swaps are needed.

\(\theta(n)\) is the cost of building a heap from scratch or of searching it, and \(\theta(n \log n)\) is heap sort, which extracts all n elements. \(\theta(n^{2})\) has no basis here.

Answer: B

A heap can be built from n numbers in O(n) time, option (B), using the bottom-up method: starting from the last internal node and sifting each node down. Most nodes are near the bottom, where the sift-down is short, and the work sums as n/4 x 1 + n/8 x 2 + n/16 x 3 + ..., which is bounded by a constant multiple of n. Inserting the n numbers one at a time costs O(n log n), which is the bound in (C) and is a common mistake, but it is not the best build time. O(log n) in (A) is the cost of a single insertion, and O(n squared) in (D) is far too large.

Answer: D

Both statements are correct, option (D). A priority queue is a data structure in which the intrinsic ordering of the elements, their priorities, does determine the result of its basic operations: a delete returns the element with the highest (or lowest) priority and not the oldest one. Its elements can be complex structures, such as records, which are ordered on one or several of their fields, with the key field supplying the priority. So S1 and S2 are both true, and (A), (B) and (C), which call at least one of them incorrect, are wrong.

Answer: D

In any n-element heap the number of nodes of height h is at most \(\left\lceil \frac{n}{2^{h + 1}} \right\rceil\), which is option (D). Nodes of height 0 (the leaves) are about half of all the nodes, those of height 1 about a quarter, and each further level roughly halves the count again.

For h = 0 the bound gives \(\lceil n/2 \rceil\) leaves, which is right, whereas \(\lceil n/2^{h} \rceil\) in (A) would allow n leaves. The options with 'greater than', (B) and (C), state a lower bound where an upper bound is needed.