harpoon.Util
Class BinHeapPriorityQueue

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

All Implemented Interfaces:

MaxPriorityQueue, Iterable, Collection

public class BinHeapPriorityQueue
extends 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 FibinocciHeap-based representation if speed becomes an issue.

Version:

$Id: BinHeapPriorityQueue.java,v 1.6 2002/04/25 00:39:51 ovy Exp $

Author:

Felix S. Klock II <pnkfelix@mit.edu>

Constructor Summary

BinHeapPriorityQueue()

BinHeapPriorityQueue(int size)

Method Summary

void	changePriority(Object item, int delta) Change the priority of this element by the specified delta.
void	clear()
boolean	contains(Object item)
Object	deleteMax() Returns and removes the Object in this with the highest priority.
int	getPriority(Object item) Returns the priority currently associated with this item.
boolean	insert(Object item, int priority) Inserts item into this, assigning it priority priority.
Iterator	iterator()
Object	peekMax() Returns the Object in this with the highest priority.
boolean	remove(Object item)
int	setPriority(Object item, int priority) Changes the priority of this Object to the new, specified value, and returns the old value
int	size()
String	toString()

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

Constructor Detail

BinHeapPriorityQueue

public BinHeapPriorityQueue()

BinHeapPriorityQueue

public BinHeapPriorityQueue(int size)

Method Detail

insert

public boolean insert(Object item,
                      int priority)

Description copied from interface: MaxPriorityQueue

Inserts item into this, assigning it priority priority.

Specified by:

insert in interface MaxPriorityQueue

Parameters:

item - Object being inserted

priority - Priority of item

getPriority

public int getPriority(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(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(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 Object peekMax()

Description copied from interface: MaxPriorityQueue

Returns the Object in this with the highest priority.

Specified by:

peekMax in interface MaxPriorityQueue

deleteMax

public 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(Object item)

Specified by:

remove in interface Collection

Overrides:

remove in class AbstractCollection

contains

public boolean contains(Object item)

Specified by:

contains in interface Collection

Overrides:

contains in class AbstractCollection

iterator

public Iterator iterator()

Specified by:

iterator in interface Iterable

Specified by:

iterator in interface Collection

Specified by:

iterator in class AbstractCollection

clear

public void clear()

Specified by:

clear in interface Collection

Overrides:

clear in class AbstractCollection

size

public int size()

Specified by:

size in interface Collection

Specified by:

size in class AbstractCollection

toString

public String toString()

Overrides:

toString in class AbstractCollection