A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 835

For heapsort, the data begins in position 0, so the children of node i are in
positions 2 i + 1 and 2 i + 2.

2.

on the internet

The code to implement the PriorityQueue is available in one file.

PriorityQueue.java Contains the implementation of the PriorityQueue

class.

exercises

IN SHORT
21.1

Describe the structure and ordering properties of the binary heap.

In a binary heap, for an item in position i where are the parent, left child,
and right child located?

21.2

Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and
2, one at a time, in an initially empty heap. Then show the result of using
the linear-time buildHeap algorithm instead.

21.3

Where could the 11th dashed line in Figures 21.17-21.20 have been?

21.4

A max heap supports insert , deleteMax , and findMax (but not deleteMin or
findMin ). Describe in detail how max heaps can be implemented.

21.5

Show the result of the heapsort algorithm after the initial construction
and then two deleteMax operations on the input in Exercise 21.3.

21.6

Is heapsort a stable sort (i.e., if there are duplicates, do the duplicate items
retain their initial ordering among themselves)?

21.7

IN THEORY
21.8

A complete binary tree of N elements uses array positions 1 through N .
Determine how large the array must be for
a. A binary tree that has two extra levels (i.e., is slightly unbalanced)

b. A binary tree that has a deepest node at depth 2 log N

c. A binary tree that has a deepest node at depth 4.1 log N

d. The worst-case binary tree

Show the following regarding the maximum item in the heap.
a.

21.9

It must be at one of the leaves

b. There are exactly N 2 ⁄ leaves

c. Every leaf must be examined to find it