This set contains practice questions on augmented data structures and on priority queues.
Question 1  Searchable stack. The ADT searchable stack is supposed to handle the following operations on on sets of data with two keys (for example, student name, and student ID number). The operations are PUSH, POP, TOP, MAKENULL, SEARCHBYKEY1, and SEARCHBYKEY2. Using the principle of augmentation of a data structure, suggest a data structure for this situation, such that PUSH, POP and both SEARCH operations take time O(log n) (n is the number of elements in the data structure at the time of the call), and the other operations take time O(1). 
Question 2  Maxstack. The ADT maxstack is like an ordinary stack, with an extra operation, MAX, which returns the maximum of the key values of the elements in the stack. Show an implementation that allows all operations to be performed in O(1) worstcase time. 
Question 3 
The ADT medianpriorityqueue (or MPQ for short).
The ADT medianpriorityqueue operates on a set of
elements with different key values, and
involves the following operations: makenull, insert, deletemedian,
makeMPQ.
It is known that the number of elements never exceeds a
given number n.
The operation makeMPQ takes a given number of
elements and inserts these globally (not one by one; recall
buildheap for a similar situation).
For deletemedian, note that
the median of a set of 2n elements is the nth smallest,
and that the median of a set of 2n+1 elements is the n+1st
smallest element.
Suggest, adapt or invent a data structure so that the
following can be achieved:

Question 4  kary heaps. A kary heap is a generalization of a standard binary heap so that there are k children per node. Give an implicit data structure implementation, with details on how to find the ith child of node j, and the parent of node j. Estimate the worstcase number of comparisons (as a function of n and k, where n is the number of elements) for a standard operation DELETEMIN. Same question for the operation INSERT. 
Question 5  kary heaps (continued). Let a kary heap with n elements be given. Let the number of DELETEMIN and INSERT operations be equal; the sequence of the operations is such that the size of the heap remains about n. Argue why a 4ary heap is best (you may need a calculator). 
Question 6 
Beap.
In 1976, Munro and Suwanda proposed the beap
(biparental heap) as a possible implementation for
a priority queuelike ADT supporting the operations
makenull, insert, deletemin and search.
A beap of
n elements should be visualized as a triangular matrix such
as the one shown below which has 10 elements.
The elements are added in crossdiagonal fashion,
so that the inherent order is 1, 2, 4, 6, 5, 9, 21, 8, 20
and 13 in the example shown below.
1 4 9 13 ... 2 5 20 ... 6 8 ... 21 ... 
Question 7  Beap (continued). Inspired by similar operations on heaps, describe how you would implement makenull, insert, search, and deletemin. 
Question 8 
Beap (continued).

Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.