jvx.geom
Class PuPriorityQueue

java.lang.Object
  jv.object.PsObject
      jvx.geom.PuPriorityQueue

All Implemented Interfaces:

java.lang.Cloneable, PsUpdateIf, java.io.Serializable

public final class PuPriorityQueue

extends PsObject

Integer heap with double keys (resp. weights) based on following special property: The ints given to the heap must be the numbers from 0 to capacity-1 and each int can be in the heap just once. As a result methods like isElement() run in O(1) time.

We call the integers in the heap elements.

Heap is used i.e. to compute a minimum spanning tree on the vertices resp. faces of a geometry with weight assigned to each edge (cp. Prim's algorithm for minimal spanning trees).

See Also:

Serialized Form

Field Summary

Fields inherited from class jv.object.PsObject

HAS_CONFIG_PANEL, HAS_INFO_PANEL, HAS_LABEL_PANEL, HAS_MATERIAL_PANEL, HAS_TEXTURE_PANEL, HAS_VECTOR_PANEL, INSPECTOR_INFO, INSPECTOR_INFO_EXT, IS_DELETED, IS_FIXED, IS_FOCUSSED, IS_PICKED, IS_SELECTED, IS_USED, NUM_TAGS

Constructor Summary

PuPriorityQueue(double[] key)
Create a priority queue that has the elements 0...key.length and the given keys.

PuPriorityQueue(int capacity)
Create an empty priority queue with a given capacity.

PuPriorityQueue(int capacity, double key)
Create a priority queue containing the elements 0,1,2,...capacity-1.

Method Summary

boolean	changeKey(int elem, double key) Changes the key assigned to an element and reorder the heap.
java.lang.Object	clone() Create a copy of the heap.
boolean	decreaseKey(int elem, double key) Decrease the key assigned to an element and reorder the heap.
void	emptyHeap() Remove all elements from heap.
boolean	enqueue(int elem, double key) Add element to heap.
boolean	enqueueOrDecrease(int elem, double key) Add element to heap.
int	extractMin() Extract the element with the smallest key of the heap.
int	getCapacity() Maximal heap size for this heap.
int	getElement(int position) Method returns the index of the element at the specified position.
int[]	getElements() Get the array, where the heap stores the elements.
int	getHeapSize() Get the number of Elements in the heap.
double	getKey(int element) Method returns the key of the specified element.
double	getKeyOfMin()
double[]	getKeys() Get the array containing the key of each element.
int	getPosition(int element) Method returns the position of the specified element in the heap.
int[]	getPositions() Get the array, where the heap stores the positions of the elements.
boolean	increaseKey(int elem, double key) Increases the key assigned to an element and reorder the heap.
boolean	isElement(int i) Check if element i is in the heap.

Methods inherited from class jv.object.PsObject

addInspector, addUpdateListener, assureInspector, clearTag, clone, clone, copy, getFather, getInfoPanel, getInspector, getName, getNumObjects, getSymbol, hasInspector, hasTag, hasUpdateListener, init, instanceOf, instanceOf, newInspector, newInspector, removeInspector, removeInspector, removeUpdateListener, setName, setParent, setSymbol, setTag, toString, update, updatePanels

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PuPriorityQueue

public PuPriorityQueue(int capacity)

Create an empty priority queue with a given capacity.

PuPriorityQueue

public PuPriorityQueue(double[] key)

Create a priority queue that has the elements 0...key.length and the given keys.

PuPriorityQueue

public PuPriorityQueue(int capacity,
                       double key)

Create a priority queue containing the elements 0,1,2,...capacity-1. All elements get the same (given) key.

Method Detail

getCapacity

public int getCapacity()

Maximal heap size for this heap.

getElements

public int[] getElements()

Get the array, where the heap stores the elements.

getElement

public int getElement(int position)

Method returns the index of the element at the specified position.

getPositions

public int[] getPositions()

Get the array, where the heap stores the positions of the elements.

getPosition

public int getPosition(int element)

Method returns the position of the specified element in the heap. If the element is not in the heap, -1 is returned.

getKeys

public double[] getKeys()

Get the array containing the key of each element.

getKey

public double getKey(int element)

Method returns the key of the specified element. Method returns the key even if the element has already been extracted from the heap.

decreaseKey

public boolean decreaseKey(int elem,
                           double key)

Decrease the key assigned to an element and reorder the heap. If the key is bigger than the actual key of the element nothing is done.

Returns:

false if element does not exist or its key is smaller than parameter key

increaseKey

public boolean increaseKey(int elem,
                           double key)

Increases the key assigned to an element and reorder the heap. If the key is smaller than the actual key of the element, nothing is done.

Returns:

false if element does not exist or its key is greater than parameter key

changeKey

public boolean changeKey(int elem,
                         double key)

Changes the key assigned to an element and reorder the heap.

Returns:

false if element does not exist

getKeyOfMin

public double getKeyOfMin()

extractMin

public int extractMin()

Extract the element with the smallest key of the heap. To get the key of the element use getKey(int).

getHeapSize

public int getHeapSize()

Get the number of Elements in the heap.

clone

public java.lang.Object clone()

Create a copy of the heap.

Overrides:

clone in class PsObject

See Also:

PsObject.copy(PsObject)

isElement

public boolean isElement(int i)

Check if element i is in the heap.

enqueue

public boolean enqueue(int elem,
                       double key)

Add element to heap. TODO:NO LONGER VALID:If element is already in the heap nothing is done and false is return.

enqueueOrDecrease

public boolean enqueueOrDecrease(int elem,
                                 double key)

Add element to heap. If the element is already in the heap and the given key is smaller than the actual key, decrease its key.

emptyHeap

public void emptyHeap()

Remove all elements from heap.