Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Util >> [ Collections overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

Util.Collections
Class BinHeapPriorityQueue  

java.lang.Object
  java.util.AbstractCollection
      Util.Collections.BinHeapPriorityQueue

All Implemented Interfaces:

java.util.Collection, java.lang.Iterable, MaxPriorityQueue

---

public class BinHeapPriorityQueue

extends java.util.AbstractCollection

implements MaxPriorityQueue

BinHeapPriorityQueue is an implementation of the PriorityQueue interface. It supports O(1) time peekMax and O(lg n) time insert and removeMax operations, assuming that ArrayList is implemented in a reasonable manner. The remove operation is probably slow however. Look into implementing a FibonacciHeap-based representation if speed becomes an issue.

Version:

$Id: BinHeapPriorityQueue.java,v 1.1 2003/06/16 17:22:06 joewhaley Exp $

---

Nested Class Summary
(package private)  class	BinHeapPriorityQueue.Entry
(package private)  class	BinHeapPriorityQueue.HeapIterator

 

Field Summary
private static int	DEFAULT_SIZE
private  BinHeapPriorityQueue.Entry[]	heap
private  java.util.HashMap	item2entry
private  int	size

 

Constructor Summary

BinHeapPriorityQueue()

BinHeapPriorityQueue(int size)

 

Method Summary
void	changePriority(java.lang.Object item, int delta)           Change the priority of this element by the specified delta.
void	clear()           Clear the collection, such that a subsequent call to isEmpty() would return true.
boolean	contains(java.lang.Object item)           Test whether this collection contains a given object as one of its elements.
java.lang.Object	deleteMax()           Returns and removes the Object in this with the highest priority.
private  void	ensureCapacity(int size)
int	getPriority(java.lang.Object item)           Returns the priority currently associated with this item.
boolean	insert(java.lang.Object item, int priority)           Inserts item into this, assigning it priority priority.
java.util.Iterator	iterator()           Obtain an Iterator over this collection.
java.lang.Object	peekMax()           Returns the Object in this with the highest priority.
private  void	percolate(BinHeapPriorityQueue.Entry entry)
private  void	priorityChanged(BinHeapPriorityQueue.Entry entry, int delta)
boolean	remove(java.lang.Object item)           Remove a single occurrence of an object from this collection.
private  void	removeEntry(BinHeapPriorityQueue.Entry entry)
int	setPriority(java.lang.Object item, int priority)           Changes the priority of this Object to the new, specified value, and returns the old value
private  void	siftDown(BinHeapPriorityQueue.Entry entry)
int	size()           Get the number of elements in this collection.
private  void	swap(BinHeapPriorityQueue.Entry e1, BinHeapPriorityQueue.Entry e2)
java.lang.String	toString()           Creates a String representation of the Collection.

 

Methods inherited from class java.util.AbstractCollection

add, addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toArray

 

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

 

Methods inherited from interface java.util.Collection

add, addAll, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

 

Field Detail

item2entry

private java.util.HashMap item2entry

---

heap

private BinHeapPriorityQueue.Entry[] heap

---

size

private int size

---

DEFAULT_SIZE

private static final int DEFAULT_SIZE

See Also:

Constant Field Values

Constructor Detail

BinHeapPriorityQueue

public BinHeapPriorityQueue()

---

BinHeapPriorityQueue

public BinHeapPriorityQueue(int size)

Method Detail

insert

public boolean insert(java.lang.Object item,
                      int priority)

Description copied from interface: MaxPriorityQueue

Inserts item into this, assigning it priority priority.

Specified by:

insert in interface MaxPriorityQueue

---

getPriority

public int getPriority(java.lang.Object item)

Description copied from interface: MaxPriorityQueue

Returns the priority currently associated with this item.

Specified by:

getPriority in interface MaxPriorityQueue

---

setPriority

public int setPriority(java.lang.Object item,
                       int priority)

Description copied from interface: MaxPriorityQueue

Changes the priority of this Object to the new, specified value, and returns the old value

Specified by:

setPriority in interface MaxPriorityQueue

---

changePriority

public void changePriority(java.lang.Object item,
                           int delta)

Description copied from interface: MaxPriorityQueue

Change the priority of this element by the specified delta. This is equivalent to setPriority(item, getPriority(item)+delta). It might save time in some implementations.

Specified by:

changePriority in interface MaxPriorityQueue

---

peekMax

public java.lang.Object peekMax()

Description copied from interface: MaxPriorityQueue

Returns the Object in this with the highest priority.

Specified by:

peekMax in interface MaxPriorityQueue

---

deleteMax

public java.lang.Object deleteMax()

Description copied from interface: MaxPriorityQueue

Returns and removes the Object in this with the highest priority.

Specified by:

deleteMax in interface MaxPriorityQueue

---

remove

public boolean remove(java.lang.Object item)

Description copied from interface: java.util.Collection

Remove a single occurrence of an object from this collection. That is, remove an element e, if one exists, such that o == null ? e == null : o.equals(e).

Specified by:

remove in interface java.util.Collection

---

contains

public boolean contains(java.lang.Object item)

Description copied from interface: java.util.Collection

Test whether this collection contains a given object as one of its elements.

Specified by:

contains in interface java.util.Collection

---

iterator

public java.util.Iterator iterator()

Description copied from interface: java.util.Collection

Obtain an Iterator over this collection.

Specified by:

iterator in interface java.util.Collection

---

clear

public void clear()

Description copied from interface: java.util.Collection

Clear the collection, such that a subsequent call to isEmpty() would return true.

Specified by:

clear in interface java.util.Collection

---

size

public int size()

Description copied from interface: java.util.Collection

Get the number of elements in this collection.

Specified by:

size in interface java.util.Collection

---

toString

public java.lang.String toString()

Description copied from class: java.util.AbstractCollection

Creates a String representation of the Collection. The string returned is of the form "[a, b, ...]" where a and b etc are the results of calling toString on the elements of the collection. This implementation obtains an Iterator over the Collection and adds each element to a StringBuffer as it is returned by the iterator. "" is inserted when the collection contains itself (only works for direct containment, not for collections inside collections).

---

removeEntry

private void removeEntry(BinHeapPriorityQueue.Entry entry)

---

ensureCapacity

private void ensureCapacity(int size)

---

priorityChanged

private void priorityChanged(BinHeapPriorityQueue.Entry entry,
                             int delta)

---

percolate

private void percolate(BinHeapPriorityQueue.Entry entry)

---

siftDown

private void siftDown(BinHeapPriorityQueue.Entry entry)

---

swap

private void swap(BinHeapPriorityQueue.Entry e1,
                  BinHeapPriorityQueue.Entry e2)

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Util >> [ Collections overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---