Package aud

Class PriorityQueue<T>

java.lang.Object
aud.adt.AbstractPriorityQueue<T>
aud.PriorityQueue<T>
public class PriorityQueue<T> extends AbstractPriorityQueue<T>
Priority queue based on binary min-heap.

This data structure additionally allows for limited set semantics (contains(T)) and updating priorities of contained entries: lower(T), raise(T).

This functionality is required, e.g., by Dijkstra's algorithm. It is implemented as an additional HashMap that maps entries T (keys) to position_s (values), i.e., for any entry we know its position in the heap and can therefore apply upheap(int) and downheap(int).

Note that using the above feature requires that entries in the PQ are unique! Therefore push(T) throws an exception if the same entry (tested by equals) is added twice!

Hint: For an efficient implementation of Dijkstra's algorithm, it is usually better to store the map position_ as an int attribute of nodes in the graph (efficient and direct access). This, however, requires that the implementation of the graph data structure and the priority queue are closely coupled.

Note: You can alternatively use Java's java.util.PriorityQueue to implement Dijkstra's algorithm. In this case you need to replace lower(T) by calling remove followed by add, which changes priority.
Note that, e.g., the C++ standard library provides only a data structure std::priority_queue that does neither provide direct update of priority nor removal of arbitrary entries! (You need to implement you own data structure similar to this one!)

  • Constructor Details

    • PriorityQueue

      public PriorityQueue(int n, Comparator<T> cmp)
      Create empty priority queue
      Parameters:
      n - expected number of entries (preallocates/reserves storage)
      cmp - compare entries

    • PriorityQueue

      public PriorityQueue(Comparator<T> cmp)

    • PriorityQueue

      public PriorityQueue(int n)

    • PriorityQueue

      public PriorityQueue()

  • Method Details

    • front

      public T front()
      Description copied from class: AbstractPriorityQueue
      Get minimal element. Requires !is_empty().
      Specified by:
      front in class AbstractPriorityQueue<T>
      Returns:
      top

    • is_empty

      public boolean is_empty()
      Description copied from class: AbstractPriorityQueue
      Is PQ empty?
      Specified by:
      is_empty in class AbstractPriorityQueue<T>

    • contains

      public boolean contains(T x)
      Is x contained in PQ?

    • size

      public int size()
      get number of entries

    • pop

      public T pop()
      Description copied from class: AbstractPriorityQueue
      Pop minimal element from PQ. Requires !is_empty().
      Specified by:
      pop in class AbstractPriorityQueue<T>
      Returns:
      removed (minimal) element

    • push

      public void push(T x)
      Add entry to PQ.
      Specified by:
      push in class AbstractPriorityQueue<T>
      Parameters:
      x - new entry that must not be already contained in PQ
      Throws:
      RuntimeException - if x is already contained in PQ

    • raise

      public void raise(T x)
      update heap after raising priority of x

    • lower

      public void lower(T x)
      update heap after lowering priority of x

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • checkConsistency

      public void checkConsistency()
      check consistency

    • main

      public static void main(String[] args)
      example and test