Homework 8

CS409 - Spring 2000

Due: Thursday, Apr 6

For this assignment, you are to implement another kind of "priority queue".  The data structure is not a standard PQ because it allows some nonstandard operations.  Also, this structure is more restricted in some ways than a typical PQ.  To simplify the discussion, I'm going to call this structure a Binary Priority Queue (BPQ).

A BPQ is restricted to holding integers in the range 0 to u-1; u is called the universe size.  The binary part of the data type's name comes from the restriction that each item in the universe-range is either in or not-in the BPQ; multiple copies of an item are not represented in the BPQ.  Operations for a BPQ include Insert, Delete, GetMin, and GetMax.  In addition, there are two new operations: GetPreceding and GetFollowing.  GetPreceding(k) returns the item currently in the BPQ that most closely precedes k. Similarly, GetFollowing(k) returns the item currently in the BPQ that most closely follows k.  Note that for both operations, k itself may or may not be in the BPQ.

Our implementation will be written to force u to be a power of 2.  Note that if an arbitrary integer is rounded up to a power of 2 then the size at most doubles, so rounding to the next higher power of 2 does not have a significant effect on either the space used by the data structure or the running times of the operations. 

A BPQ can be implemented so that O(u) space is used and so that all the operations mentioned above run in time O(log u) where u is the universe size.  Note that the running time does not depend on n, the number of items in the BPQ. 

The BPQ is held in a binary tree with u leaves, numbered u to 2u-1.  The tree is actually held in an array.  We use the same trick we used for the heap data structure to determine the parents and children of a given node: the parent of node i is located at i/2 and the children of node i are in locations 2i and 2i+1.  Each node of the tree holds a single bit.

Each item in the universe corresponds to a leaf in the tree.  Note that the leaf index-numbers do not match the item numbers: item k corresponds to the leaf with index u+k.  When an item is inserted, we turn on the bit in the corresponding leaf node.  We also turn on all the bits on the path from the tree's root to this leaf node.  Since the tree's height is O(log u), this takes time O(log u).  The Delete operation is a little more complicated because a bit in a nonleaf node can be on due to more than one leaf node.  The GetPreceding and GetFollowing operations can be implemented by starting at a leaf and exploring the path toward the root until we find a branch in the right direction; the desired item is found by following that branch back to a leaf node.

Here are the operations, in Java form, that your BPQ needs to handle:

• public BPQ(int u);
  Create a BPQ of the given size, after rounding u up to a power of 2 if necessary.
• public int universe ();
  Return u, the size of the universe (i.e., the size after rounding to a power of 2).
• public void insert (int item);
  Insert a new item. Nothing happens if the item is already present in the BPQ. It is an error (i.e., throw an IllegalArgumentException) if item is not within 0..u-1.
• public void delete (int item);
  Delete an item. Nothing happens if the item is not a member of this BPQ and nothing happens if the item is not within 0..u-1.
• public boolean contains (int item);
  Return true iff the item is currently in the BPQ.  False is returned for items not within 0..u-1.
• public boolean isEmpty ();
  Return true iff the BPQ is currently empty.
• public int getMin ();
  Determine the smallest item in the BPQ. Throws a java.util.NoSuchElementException if empty.
• public int getMax ();
  Determine the largest item in the BPQ. Throws a java.util.NoSuchElementException if empty.
• public int getPreceding (int value);
  Determine the preceding item. If there is no preceding item then return -1.
• public int getFollowing (int value);
  Determine the following item. If there is no following item then return -1.
• public String toString ();
  Return a String representation of this BPQ.

What to Turn in:

• A listing of your BPQ class.
• The output from the test program.  The test program is a main() method (held in a .txt file) that should be included in your BPQ class. You can download it by right-clicking on the link. Since J++ can read a text file, it's easy to transfer the main() method into your own BPQ class.

Some Notes/Hints on the BPQ:

• As outlined above, the array that holds the tree does not make use of position 0. This wastes one array position, but it allows the child/parent calculation to be a small amount easier.
• It's probably more space-efficient to use a java.util.BitSet rather than an a boolean array, but operations are probably somewhat faster if a boolean array is used. You're welcome to use either one.
• You may find it useful to use the shift operators: k<<n does a left shift of the number k by n positions (in other words, 1<<n is a fast way to compute 2ⁿ); k>>n does a right shift of the number k by n positions (the low-order bits are lost)
• This BPQ data structure is the basis for a more complicated data structure developed by van Emde Boas [P. van Emde Boas, R. Kaas, and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory 10, 99-127, 1977].  His data structure, in effect, uses binary search on the root-to-leaf  paths of our BPQ implementation to speed up the above operations, achieving a running time of O(loglog u) per operation.