aud.PriorityQueue< T > Class Template Reference

Priority queue based on binary min-heap. More...

Inheritance diagram for aud.PriorityQueue< T >:

Collaboration diagram for aud.PriorityQueue< T >:

Public Member Functions
	PriorityQueue (int n, Comparator< T > cmp)
	Create empty priority queue. More...
	PriorityQueue (Comparator< T > cmp)
	PriorityQueue (int n)
	PriorityQueue ()
T	front ()
	Get minimal element. More...
boolean	is_empty ()
	Is PQ empty? More...
boolean	contains (T x)
	Is x contained in PQ? More...
int	size ()
	get number of entries More...
T	pop ()
	Pop minimal element from PQ. More...
void	push (T x)
	Add entry to PQ. More...
void	raise (T x)
	update heap after raising priority of x More...
void	lower (T x)
	update heap after lowering priority of x More...
String	toString ()
void	checkConsistency ()
	check consistency More...
abstract boolean	is_empty ()
	Is PQ empty? More...
abstract T	front ()
	Get minimal element. More...
abstract T	pop ()
	Pop minimal element from PQ. More...
abstract void	push (T x)
	Push x into PQ. More...

Static Public Member Functions
static void	main (String[] args)
	example and test More...

Additional Inherited Members
Protected Member Functions inherited from aud.adt.AbstractPriorityQueue< T >
	AbstractPriorityQueue (java.util.Comparator< T > cmp)
	create empty PQ and use cmp_ for comparison of priorities More...
	AbstractPriorityQueue ()
	create empty PQ More...
boolean	less (T a, T b)
	test for a<b, uses Comparator if one was provided or Comparable else. More...
Protected Attributes inherited from aud.adt.AbstractPriorityQueue< T >
Comparator< T >	cmp_ = null

Detailed Description

Priority queue based on binary min-heap.

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

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 and downheap.

Note that using the above feature requires that entries in the PQ are unique! Therefore push 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 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!)

Definition at line 46 of file PriorityQueue.java.

Constructor & Destructor Documentation

PriorityQueue() [1/4]

aud.PriorityQueue< T >.PriorityQueue	(	int	n,
		Comparator< T >	cmp
	)

Create empty priority queue.

Parameters

n	expected number of entries (preallocates/reserves storage)
cmp	compare entries

Definition at line 65 of file PriorityQueue.java.

                                                {
    super(cmp);
    heap_=new Vector<T>();
    heap_.reserve(n);
    position_=new HashMap<T,Integer>(n);
  }

PriorityQueue() [2/4]

aud.PriorityQueue< T >.PriorityQueue

(

Comparator< T >

cmp

)

Definition at line 71 of file PriorityQueue.java.

{ this(MINENTRIES,cmp); }

PriorityQueue() [3/4]

aud.PriorityQueue< T >.PriorityQueue

(

int

n

)

Definition at line 73 of file PriorityQueue.java.

{ this(n,null); }

PriorityQueue() [4/4]

aud.PriorityQueue< T >.PriorityQueue

(

)

Definition at line 74 of file PriorityQueue.java.

{ this(MINENTRIES,null); }

Member Function Documentation

checkConsistency()

void aud.PriorityQueue< T >.checkConsistency

(

)

check consistency

Definition at line 203 of file PriorityQueue.java.

                                 {
    System.err.println("size="+heap_.size());
    // check mapping between heap_ and position_
    if (heap_.size()!=position_.size())
      throw new RuntimeException("size mismatch");
    for (int i=0;i<heap_.size();++i)
      if (position_.find(heap_.at(i))==null || position_.find(heap_.at(i))!=i)
        throw new RuntimeException("invalid mapping for key='"+heap_.at(i)+"'");
 
    // check heap property
    for (int i=0;i<heap_.size();++i) {
      if (i>0) {
        int p=getParent(i);
        if (!leq(p,i))
          throw new RuntimeException("heap property violated (parent");
      }
      int left=getLeftChild(i);
      if (left<heap_.size()) {
        if (!leq(i,left))
          throw new RuntimeException("heap property violated (left)");
 
        int right=left+1;
        if (right<heap_.size()) {
          if (!leq(i,right))
            throw new RuntimeException("heap property violated (right)");
        }
      }
    }
  }

contains()

boolean aud.PriorityQueue< T >.contains

(

T

x

)

Is x contained in PQ?

Definition at line 85 of file PriorityQueue.java.

{ return position_.contains(x); }

Referenced by aud.PriorityQueue< T >.push().

Here is the caller graph for this function:

front()

T aud.PriorityQueue< T >.front

(

)

Get minimal element.

Requires !is_empty().

Exceptions

NoSuchElementException

Returns

top

Reimplemented from aud.adt.AbstractPriorityQueue< T >.

Definition at line 76 of file PriorityQueue.java.

                             {
    return heap_.front(); // may throw
  }

Referenced by aud.PriorityQueue< T >.main().

Here is the caller graph for this function:

is_empty()

boolean aud.PriorityQueue< T >.is_empty

(

)

Is PQ empty?

Reimplemented from aud.adt.AbstractPriorityQueue< T >.

Definition at line 80 of file PriorityQueue.java.

                                      {
    return heap_.empty();
  }

Referenced by aud.example.graph.PriorityFirstSearch.start().

Here is the caller graph for this function:

lower()

void aud.PriorityQueue< T >.lower

(

T

x

)

update heap after lowering priority of x

Definition at line 187 of file PriorityQueue.java.

                         {
    assert(position_.contains(x));
    int k=position_.find(x);
 
    // Assert that priority was lowered!
    assert(getLeftChild(k)  >=heap_.size() || less(k,getLeftChild(k)));
    assert(getLeftChild(k)+1>=heap_.size() || less(k,getLeftChild(k)+1));
 
    upheap(k);
  }

Referenced by aud.PriorityQueue< T >.main().

Here is the caller graph for this function:

main()

static void aud.PriorityQueue< T >.main ( String[]  args )

static

example and test

Definition at line 234 of file PriorityQueue.java.

                                         {
 
    {
      // use as a "standard" priority queue
 
      PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
 
      pq.push(2); System.out.println(pq);
      pq.push(4); System.out.println(pq);
      pq.push(3); System.out.println(pq);
      pq.push(1); System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
    }
    {
      // now the following provides a mapping from entries to priorities
      final HashMap<String,Integer> priority=new HashMap<String,Integer>();
      priority.insert("a",1);
      priority.insert("b",2);
      priority.insert("c",3);
      priority.insert("d",4);
 
      PriorityQueue<String> pq=
        new PriorityQueue<String>
        (new Comparator<String>() {
          @Override public int compare(String a,String b) {
            return priority.find(a)-priority.find(b);
          }
        });
 
      // first we do the same as above
 
      pq.push("b"); System.out.println(pq);
      pq.push("d"); System.out.println(pq);
      pq.push("c"); System.out.println(pq);
      pq.push("a"); System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      // restore what we had before
      pq.push("b"); System.out.println(pq);
      pq.push("a"); System.out.println(pq);
 
      // now we gonna change the priority mapping and update pq
 
      System.out.println("front="+pq.front());
      priority.insert("a",5); // RAISE priority ...
      System.out.println("new prioities: "+priority);
      pq.raise("a");         // ... and update pq
      System.out.println("front="+pq.front());
      priority.insert("c",0); // LOWER priority ...
      System.out.println("new prioities: "+priority);
      pq.lower("c");         // ... and update pq
      System.out.println("front="+pq.front());
    }
  }

References aud.HashMap< Key, Value >.find(), aud.PriorityQueue< T >.front(), aud.HashMap< Key, Value >.insert(), aud.PriorityQueue< T >.lower(), aud.PriorityQueue< T >.pop(), aud.PriorityQueue< T >.push(), and aud.PriorityQueue< T >.raise().

Here is the call graph for this function:

pop()

T aud.PriorityQueue< T >.pop

(

)

Pop minimal element from PQ.

Requires !is_empty().

Exceptions

NoSuchElementException

Returns

removed (minimal) element

Reimplemented from aud.adt.AbstractPriorityQueue< T >.

Definition at line 90 of file PriorityQueue.java.

                           {
    T root=heap_.front(); // may throw
    position_.remove(root);
 
    if (heap_.size()>1) {
      position_.insert((heap_.data_[0]=heap_.back()),0);
      heap_.pop_back();
      downheap(0);
    }
    else
      heap_.pop_back();
 
    return root;
  }

Referenced by aud.PriorityQueue< T >.main(), and aud.example.graph.PriorityFirstSearch.start().

Here is the caller graph for this function:

push()

void aud.PriorityQueue< T >.push

(

T

x

)

Add entry to PQ.

Parameters

x	new entry that must not be already contained in PQ

Exceptions

RuntimeException

if x is already contained in PQ

Reimplemented from aud.adt.AbstractPriorityQueue< T >.

Definition at line 153 of file PriorityQueue.java.

                                  {
    if (contains(x))
      throw new RuntimeException(x.toString()+" already contained in PQ");
 
    int k=heap_.size();
    heap_.push_back(x);
    position_.insert(x,k);
    upheap(k);
  }

References aud.PriorityQueue< T >.contains().

Referenced by aud.example.grid.Grid.astar(), aud.example.grid.Grid2.astar(), aud.example.grid.Grid.dijkstra(), aud.example.grid.Grid2.dijkstra(), aud.PriorityQueue< T >.main(), and aud.example.graph.PriorityFirstSearch.start().

Here is the call graph for this function:

Here is the caller graph for this function:

raise()

void aud.PriorityQueue< T >.raise

(

T

x

)

update heap after raising priority of x

Definition at line 177 of file PriorityQueue.java.

                         {
    assert(position_.contains(x));
    int k=position_.find(x);
 
    assert(k==0 || less(getParent(k),k));   // priority was raised!
 
    downheap(k);
  }

Referenced by aud.PriorityQueue< T >.main().

Here is the caller graph for this function:

size()

int aud.PriorityQueue< T >.size

(

)

get number of entries

Definition at line 88 of file PriorityQueue.java.

{ return heap_.size(); }

toString()

String aud.PriorityQueue< T >.toString

(

)

Definition at line 198 of file PriorityQueue.java.

                                     {
    return position_.toString();
  }

Referenced by aud.example.graph.PriorityFirstSearch.start().

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• PriorityQueue.java