il2.inf.structure.minfill2
Class IntPriorityQueue

Object
  extended by PriorityQueue
      extended by IntPriorityQueue

public class IntPriorityQueue
extends PriorityQueue

A priority queue implemented with a heap where elements are ints in [0,N-1] for some N, where keys are doubles, where lower keys are higher priority, and where the queue may not contain duplicate items. The size of the queue is linear in N, so N should not be outrageous.

Author:
Mark Chavira

Constructor Summary
IntPriorityQueue(int N)
          Initializes an empty priority queue.
IntPriorityQueue(int N, int[] elems, double[] keys)
          Initializes the priority queue with the given elements.
 
Method Summary
 void add(int e, double k)
          Inserts the given element into the queue.
 void clear()
          Resets the priority queue.
 void clear(int[] elems, double[] keys)
          Clears the priority queue and then adds the given elements.
 boolean contains(int e)
          Returns whether the queue contains the given element.
 int highest()
          Returns the highest priority element.
 double highestKey()
          Returns the highest priority key.
 void incrementKey(int e, double delta)
          Changes the key of the given element by the given value.
 int nthElement(int n)
          Returns the nth element in the priority queue, where n indicates how the elements are stored not their priority.
 double nthKey(int n)
          Returns the nth key in the priority queue, where n indicates how the elements are stored not their priority.
 int remove()
          Removes and returns the highest priority element.
 void setKey(int e, double k)
          Sets the key of the given element to the given value.
 int size()
          Returns the number of elements in the queue.
 String toString()
           
 
Methods inherited from class PriorityQueue
validateHeapProperty
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

IntPriorityQueue

public IntPriorityQueue(int N,
                        int[] elems,
                        double[] keys)
                 throws Exception
Initializes the priority queue with the given elements. This method runs in time linear in the number of elements, and is thus faster than creating a priority queue and then adding the elements.

Parameters:
N - defines the elements that may be entered into the queue.
elems - the given elements.
keys - the given elements' keys.
Throws:
Exception

IntPriorityQueue

public IntPriorityQueue(int N)
Initializes an empty priority queue.

Parameters:
N - defines the elements that may be entered into the queue.
Method Detail

size

public int size()
Description copied from class: PriorityQueue
Returns the number of elements in the queue.

Specified by:
size in class PriorityQueue
Returns:
the number of elements.
See Also:
PriorityQueue

clear

public void clear()
Description copied from class: PriorityQueue
Resets the priority queue.

Specified by:
clear in class PriorityQueue
See Also:
PriorityQueue

clear

public void clear(int[] elems,
                  double[] keys)
           throws Exception
Clears the priority queue and then adds the given elements.

Parameters:
elems - the given elements.
keys - the given elements' keys.
Throws:
Exception

add

public void add(int e,
                double k)
         throws Exception
Inserts the given element into the queue.

Parameters:
e - the given element.
k - the given element's key.
Throws:
Exception

highest

public int highest()
Returns the highest priority element.

Returns:
the highest priority element.

highestKey

public double highestKey()
Returns the highest priority key.

Returns:
the highest priority key.

contains

public boolean contains(int e)
Returns whether the queue contains the given element.

Parameters:
e - the given element.
Returns:
whether the queue constains the given element.

setKey

public void setKey(int e,
                   double k)
            throws Exception
Sets the key of the given element to the given value.

Parameters:
e - the given element.
k - the given key.
Throws:
Exception

incrementKey

public void incrementKey(int e,
                         double delta)
                  throws Exception
Changes the key of the given element by the given value.

Parameters:
e - the given element.
delta - the given value.
Throws:
Exception

remove

public int remove()
Removes and returns the highest priority element. This method runs in time logarithmic in the size of the heap.

Returns:
the removed integer.

nthElement

public int nthElement(int n)
Returns the nth element in the priority queue, where n indicates how the elements are stored not their priority.

Parameters:
n - identifies the element.
Returns:
the nth element.

nthKey

public double nthKey(int n)
Returns the nth key in the priority queue, where n indicates how the elements are stored not their priority.

Parameters:
n - identifies the element.
Returns:
the nth key.

toString

public String toString()
Overrides:
toString in class Object
See Also:
Object


Copyright 2010 UCLA Automated Reasoning Group