cc.mallet.util.search
Class MinHeap

java.lang.Object
  cc.mallet.util.search.MinHeap

All Implemented Interfaces:

PriorityQueue

public class MinHeap
extends java.lang.Object
implements PriorityQueue

Created by IntelliJ IDEA. User: pereira Date: Jun 18, 2005 Time: 9:11:24 PM

Binary heap implementation of PriorityQueue. Based on algorithm in Corman, Leiserson, Rivest, and Stein (Section 6.5).

Constructor Summary

MinHeap()
Create a binary heap with minimum initial capacity.

MinHeap(int capacity)
Create a binary heap with initial capacity capacity.

Method Summary

void	changePriority(QueueElement e, double priority) Change the priority of queue element e to priority.
boolean	contains(QueueElement e) Does the queue contain an element?
QueueElement	extractMin() Remove the top element of the queue.
void	insert(QueueElement e) Insert element e into the queue.
QueueElement	min() Return the top element of the queue.
int	size() The current size of the queue.
QueueElement[]	toArray() Returns any array containing all of the elements in the queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

MinHeap

public MinHeap(int capacity)

Create a binary heap with initial capacity capacity. The heap's capacity grows as needed to accomodate insertions.

Parameters:

capacity - initial capacity

MinHeap

public MinHeap()

Create a binary heap with minimum initial capacity.

Method Detail

size

public int size()

Description copied from interface: PriorityQueue

The current size of the queue.

Specified by:

size in interface PriorityQueue

Returns:

current size

min

public QueueElement min()

Description copied from interface: PriorityQueue

Return the top element of the queue.

Specified by:

min in interface PriorityQueue

Returns:

top element of the queue

extractMin

public QueueElement extractMin()

Description copied from interface: PriorityQueue

Remove the top element of the queue.

Specified by:

extractMin in interface PriorityQueue

Returns:

the element removed

changePriority

public void changePriority(QueueElement e,
                           double priority)

Description copied from interface: PriorityQueue

Change the priority of queue element e to priority. The element's position in the queue is adjusted as needed.

Specified by:

changePriority in interface PriorityQueue

Parameters:

e - the element that has been changed

priority - the new priority

insert

public void insert(QueueElement e)

Description copied from interface: PriorityQueue

Insert element e into the queue.

Specified by:

insert in interface PriorityQueue

Parameters:

e - the element to insert

contains

public boolean contains(QueueElement e)

Description copied from interface: PriorityQueue

Does the queue contain an element?

Specified by:

contains in interface PriorityQueue

Parameters:

e - the element

Returns:

whether the queue contains the element

toArray

public QueueElement[] toArray()

Description copied from interface: PriorityQueue

Returns any array containing all of the elements in the queue. They are not guaranteed to be in any particular order.

Specified by:

toArray in interface PriorityQueue