CSC 302 UNLV Implementation of Updatable Priority Queue as a Heap


We will define an item to be an ordered pair (ID,KEY). We will also assume that no two items have the same ID. An updatable priority queue (UPQ) has the following operators.
  1. Initialize the UPQ to be empty.
  2. Check whether the UPQ is empty.
  3. Insert an item into the UPQ.
  4. Delete an item of minimum KEY from the UPQ.
  5. Check whether an item with a given ID is in the UPQ.
  6. Change the value of KEY for an item which is already in the UPQ.
There are many ways to implementat the ADT UPQ. We given one example below.
We can implement a UPQ as a heap, and we can use the standard array implementation of a heap. We will need the following parts to our data structure:
  1. An array key[ i ] showing the current KEY value of the item whose ID is i.
  2. A Boolean array inUPQ[ i ] showing wether the item whose ID is i is in the UPQ.
  3. An array A[ j ] indexed from 1 to n, where n is at least as large as the maximum number of items that will be in the UPQ at any one time. A[ j ] is the ID of the item in position j of the heap. You do not need to store KEY values in the heap.
  4. A non-negative integer sizeUPQ giving the number of items currently in the UPQ.
  5. An array locationInUPQ[ i ] giving the current location, in A, of the item whose ID is i.

Implementation of the Operators.
  1. Initialize is implemented by setting sizeUPQ to zero.
  2. Check whether the UPQ is empty by checking whether sizeUPQ is zero.
  3. You will need the usual heap operations of bubbleup and bubbledown. However, whenever you swap values in A, you must make sure to change the values of the array inUPQ. This swap can be implemented as follows. Suppose j1 and j2 are locations in the array A. You swap them by executing the following six statements:
    • i1 = A[ j1 ], the ID of the item in position j1 of the heap.
    • i2 = A[ j2 ], the ID of the item in position j2 of the heap.
    • A[ j1 ] = i2; A[ j2 ] = i1; locatinInUPQ[ i1 ] = j2; locationInUPQ[ i2 ] = j1.
    Bubbleup( j ) and Bubbledown( j ) are implemented in the usual manner. But you do not compare the values of A[ j1 ] and A[ j2 ]. Instead, you compare values of key[ A [ j1 ] ] and key[ A [ j2 ] ].
  4. You implement insert( i ) by sizeUPQ++; A[ sizeUPQ ] = i; inUPQ[ i ] = true; bubbleup( sizeUPQ ).
  5. You implement delete minimum by i = A[ 1 ]; A[ 1 ] = A[ sizeUPQ ]; sizeUPQ - -; inUQP[ i ] = false; bubbledown( 1 ); return i.
  6. Check whether the item with ID i is in the UPQ by checking the Boolean inUPQ[ i ].
  7. You implement update( i, k ), as follows.
    If k < key[ i ], then key[ i ] = k; bubbleup( locationInUPQ[ i ] ).
    If k > key[ i ], then key[ i ] = k; bubbledown( locationInUPQ[ i ] ).