com.infomatiq.jsi

Class PriorityQueue

java.lang.Object

com.infomatiq.jsi.PriorityQueue

public class PriorityQueue
extends Object

Priority Queue that stores values as ints and priorities as floats. Uses a Heap to sort the priorities; the values are sorted "in step" with the priorities.

A Heap is simply an array that is kept semi sorted; in particular if the elements of the array are arranged in a tree structure; ie

                                   00
                                 /     \
                             01          02
                            /  \        /  \
                          03    04    05    06
                          /\    /\    /\    /\
                        07 08 09 10 11 12 13 14
 

then each parent is kept sorted with respect to it's immediate children. E.g. 00 < 01, 00 < 02, 02 < 05, 02 < 06

This means that the array appears to be sorted, as long as we only ever look at element 0.

Inserting new elements is much faster than if the entire array was kept sorted; a new element is appended to the array, and then recursively swapped with each parent to maintain the "parent is sorted w.r.t it's children" property.

To return the "next" value it is necessary to remove the root element. The last element in the array is placed in the root of the tree, and is recursively swapped with one of it's children until the "parent is sorted w.r.t it's children" property is restored.

Random access is slow (eg for deleting a particular value), and is not implemented here - if this functionality is required, then a heap probably isn't the right data structure.

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	SORT_ORDER_ASCENDING
static boolean	SORT_ORDER_DESCENDING

Constructor Summary

Constructors

Constructor and Description
PriorityQueue(boolean sortOrder)
PriorityQueue(boolean sortOrder, int initialCapacity)

Method Summary

Modifier and Type	Method and Description
void	clear()
float	getPriority()
int	getValue()
void	insert(int value, float priority)
int	pop()
void	reset()
void	setSortOrder(boolean sortOrder)
int	size()

Methods inherited from class java.lang.Object

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

Field Detail

SORT_ORDER_ASCENDING

public static final boolean SORT_ORDER_ASCENDING

See Also:

Constant Field Values

SORT_ORDER_DESCENDING

public static final boolean SORT_ORDER_DESCENDING

See Also:

Constant Field Values

Constructor Detail

PriorityQueue

public PriorityQueue(boolean sortOrder)

PriorityQueue

public PriorityQueue(boolean sortOrder,
                     int initialCapacity)

Method Detail

insert

public void insert(int value,
                   float priority)

size

public int size()

clear

public void clear()

reset

public void reset()

getValue

public int getValue()

getPriority

public float getPriority()

pop

public int pop()

setSortOrder

public void setSortOrder(boolean sortOrder)