jvx.util

## Class PuPriorityQueue

- java.lang.Object
- - jv.object.PsObject
  - - jvx.util.PuPriorityQueue

- All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, PsUpdateIf

      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 e.g. 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
  Author:
    Klaus Hildebrandt
  Version:
    01.03.07, 2.01 revised (mn) Added field m_capacity.
    09.12.06, 2.00 revised (kp) Moved to jvx.util from jvx.geom.
    07.08.06, 1.30 revised (fk) New methods `toString` and #extractElement(int) extractElement}.
    20.01.05, 1.20 revised (ep) New methods `increaseKey` and `changeKey`.
    12.02.04, 1.10 revised (kh) Renamed data[][] to m_positions and m_elements.
    00.01.03, 1.00 created (kh)

- - ### Field Summary

    - ### Fields inherited from class jv.object.PsObject

      `HAS_BOUNDARY_PANEL, 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

    Constructors
    Constructor and Description
    `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

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `boolean` | `changeKey(int element, 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 element, double key)` Decrease the key assigned to an element and reorder the heap.
    `void` | `emptyHeap()` Remove all elements from heap.
    `boolean` | `enqueue(int element, double key)` Add element to heap.
    `boolean` | `enqueueOrDecrease(int element, double key)` Add element to heap.
    `double` | `extractElement(int element)` Remove a specific element from the heap and return its key.
    `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()` Get key of minimal element.
    `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 element, double key)` Increases the key assigned to an element and reorder the heap.
    `boolean` | `isElement(int element)` Check if element i is in the heap.
    `boolean` | `isEmpty()` Returns true, if there is no element in the heap.
    `java.lang.String` | `toString()` Create a multi-line string representation with detailed information about instance variables.

    - ### 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, 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 element,
                                     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 element,
                                     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 element,
                                   double key)

      Changes the key assigned to an element and reorder the heap.
      Returns:
        false if element does not exist
      Author:
        Eike Preuss
      Version:
        20.01.05, 1.00 created (ep)

    - #### getKeyOfMin

          public double getKeyOfMin()

      Get key of minimal element.

    - #### extractMin

          public int extractMin()

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

    - #### extractElement

          public double extractElement(int element)

      Remove a specific element from the heap and return its key. If the specified element index is out of range, NaN is returned.
      Parameters:
        `element` - index of the element to extract.
      Returns:
        Key of the extracted element, or NaN if argument is no queue element.
      Author:
        Felix Kaelberer
      Version:
        07.08.2006, 1.00 created (fk)

    - #### getHeapSize

          public int getHeapSize()

      Get the number of Elements in the heap.

    - #### isEmpty

          public boolean isEmpty()

      Returns true, if there is no element 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 element)

      Check if element i is in the heap.

    - #### enqueue

          public boolean enqueue(int element,
                                 double key)

      Add element to heap. If element is already in the heap nothing is done and false is returned.

    - #### enqueueOrDecrease

          public boolean enqueueOrDecrease(int element,
                                           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.

    - #### toString

          public java.lang.String toString()

      Create a multi-line string representation with detailed information about instance variables.
      Overrides:
        `toString` in class `PsObject`
      Author:
        Felix Kaelberer
      Version:
        07.08.2006, 1.00 created (fk)

"

The software JavaView? is copyright protected. All Rights Reserved.
"