com.infomatiq.jsi
Class PriorityQueue

java.lang.Object
  extended by 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
static boolean SORT_ORDER_ASCENDING
           
static boolean SORT_ORDER_DESCENDING
           
 
Constructor Summary
PriorityQueue(boolean sortOrder)
           
PriorityQueue(boolean sortOrder, int initialCapacity)
           
 
Method Summary
 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)


Copyright © 2012. All Rights Reserved.