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

c. Give an algorithm to insert a new node into the min-max heap.

d. Give an algorithm to perform deleteMin and deleteMax .

e. Give an algorithm to perform buildHeap in linear time.

The 2-D heap is a data structure that allows each item to have two indi-
vidual keys. The deleteMin operation can be performed with respect to
either of these keys. The 2-D heap-order property is that for any node X at
even depth, the item stored at X has the smallest key #1 in its subtree, and
for any node X at odd depth, the item stored at X has the smallest key #2
in its subtree. Do the following.
a.

21.20

Draw a possible 2-D heap for the items (1, 10), (2, 9), (3, 8), (4,
7), and (5, 6).

b. Explain how to find the item with minimum key #1.

c. Explain how to find the item with minimum key #2.

d. Give an algorithm to insert a new item in the 2-D heap.

e. Give an algorithm to perform deleteMin with respect to either key.

f. Give an algorithm to perform buildHeap in linear time.

A treap is a binary search tree in which each node stores an item, two
children, and a randomly assigned priority generated when the node is
constructed. The nodes in the tree obey the usual binary search tree order,
but they must also maintain heap order with respect to the priorities. The
treap is a good alternative to the balanced search tree because balance is
based on the random priorities, rather than on the items. Thus the average
case results for binary search trees apply. Do the following.
a.

21.21

Prove that a collection of distinct items, each of which has a dis-
tinct priority, can be represented by only one treap.

b. Show how to perform insertion in a treap by using a bottom-up

algorithm.

c. Show how to perform insertion in a treap by using a top-down

algorithm.

d. Show how to perform deletion from a treap.

Explain how to place the initial set of runs on two tapes when the number
of runs is not a Fibonacci number.

21.22

IN PRACTICE
21.23

Write the percDown routine with the declaration

static void percDown( AnyType [ ] a, int index, int size )

Recall that the max heap starts at position 0, not position 1.