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.
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
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
PriorityQueue
public PriorityQueue(boolean sortOrder)
PriorityQueue
public PriorityQueue(boolean sortOrder,
int initialCapacity)
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)
Copyright © 2012. All Rights Reserved.