Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## mauda.plugin.fibheap
Class FibHeap

    java.lang.Object
      mauda.plugin.fibheap.FibHeap

All Implemented Interfaces:
  Copyable, JedasMainCompObj

Direct Known Subclasses:
  FibHeapExt

    public class FibHeap

extends java.lang.Object
implements JedasMainCompObj, Copyable

Implements and animates the data structure 'Fibonacci heap' (F-heap) and the operations defined to manipulate the structure.
F-heaps are one way of implementing priority queues. They consist of nodes ('tasks') with given keys ('priorities'). At any time, a new node may be added, the node with minimum key can be accessed or removed from the queue, the key value of a given node may be decreased, or a given node may be deleted.
Calling the constructor with an instance of `jedas.Scheduler` and adding the `FibHeap` to a `jedas.CompPanel` will animate all the operations manipulating the F-heap structure.
In addition, this class offers a simple way to analyze the actual time complexity of the individual heap operations. In order to analyze a heap manipulation, call `getCount()` after executing the respective operation.
The analysis is idealized in the following sense:

- All operations with complexity O(1) take 1 time unit.
- All other operations take 1 time unit per sub-operation (such as linking or cutting nodes).
- `deletemin()` takes l additional steps, where l equals the length of the array needed to consolidate the root list [i>l = O(log heapsize)].

Version:
  2.02 (14/08/03)
Author:
  Tobias Lauer

Field Summary
`static int` | `DETAIL`
`static int` | `MORE`
`static int` | `NONE` Detail levels of accompanying text.
`static int` | `NORMAL`
`static SubOperationQueue` | `subOperations`

Constructor Summary
`FibHeap()` Creates a new, empty FibHeap.

Method Summary
`int` | `accessmin()` Returns the minimum key in this Fibonacci heap.
`void` | `add(SubOperation so)`
`void` | `clearSubOperationQueue()`
`java.lang.Object` | `copy()`
`java.lang.Object` | `copyDS()`
`void` | `decreasekey(FibNode N, int k)` Decreases the key of the specified node to the specified value.
`java.lang.Object` | `deepCopy()` Performs a deep copy of the implemented data-structure
`int` | `delete(FibNode node)` Deletes the specified node from this Fibonacci heap.
`int` | `deletemin()` Deletes the node with minimum key in this Fibonacci heap.
`int` | `getCount()` Call this method to analyze a just completed heap operation.
`int` | `getHeapSize()`
`static boolean` | `getKeyColorMode()`
`jedas.CompObj` | `getMainCompObj()` Returns the main CompObj which to visualize in the JEDAS animation-area.
`SubOperationQueue` | `getSubOperationQueue()`
`FibNode` | `insert(int k)` Inserts a new node to this Fibonacci heap.
`boolean` | `isEmpty()`
`int` | `maxRank()` Returns the maximum possible rank of a node in this `FibHeap`.
`void` | `meld(FibHeap other)` Melds another `FibHeap` into this one.
`void` | `resetCount()` Resets the step counter to 0.
`static void` | `setKeyColorMode(boolean b)` Sets the 'key color' mode.
`static void` | `setTextMode(int mode)` Sets the 'text mode' to accompany operations by text.
`java.lang.String` | `toString()`

Methods inherited from class java.lang.Object
`equals, getClass, hashCode, notify, notifyAll, wait, wait, wait`

Field Detail

### subOperations

    public static SubOperationQueue subOperations

### NONE

    public static final int NONE

  Detail levels of accompanying text.

  See Also:
    Constant Field Values

### NORMAL

    public static final int NORMAL

See Also:
  Constant Field Values

### MORE

    public static final int MORE

See Also:
  Constant Field Values

### DETAIL

    public static final int DETAIL

See Also:
  Constant Field Values

Constructor Detail

### FibHeap

    public FibHeap()

  Creates a new, empty FibHeap.

Method Detail

### isEmpty

    public boolean isEmpty()

  Returns:
    true if this `FibHeap` is empty

### meld

    public void meld(FibHeap other)

  Melds another `FibHeap` into this one. The other rootlist is inserted to the right of the given node.

  Parameters:
    `other` - the `FibHeap` to be joined with this one

### insert

    public FibNode insert(int k)

  Inserts a new node to this Fibonacci heap. Creates a new `FibNode` with given key and inserts in rootlist right of the `min` node.

  Parameters:
    `k` - key of new FibNode
  Returns:
    new FibNode with key k

### accessmin

    public int accessmin()

  Returns the minimum key in this Fibonacci heap. If FibHeap is empty, returns -1.

  Returns:
    minimum key (or 999)

### deletemin

    public int deletemin()

  Deletes the node with minimum key in this Fibonacci heap. Then consolidates rootlist to restore heap.

  Returns:
    minimum key

### decreasekey

    public void decreasekey(FibNode N,
                            int k)

  Decreases the key of the specified node to the specified value. If necessary (to restore heap), cuts the node off its parent and inserts into rootlist. In this case, the parent will then be marked, or, if marked already, also cut off, and so on.

  Parameters:
    `N` - node whose key is to be decreased
    `k` - new key value

### delete

    public int delete(FibNode node)

  Deletes the specified node from this Fibonacci heap. If the node is the min node, the `deletemin` method will be carried out.

  Parameters:
    `node` - node to be deleted
  Returns:
    key of the deleted node

### getHeapSize

    public int getHeapSize()

  Returns:
    the number of nodes in this Fibonacci heap

### getCount

    public int getCount()

  Call this method to analyze a just completed heap operation. This will give you that operation's actual time complexity (see class intro for more details).

  Returns:
    the current value of the step counter.

### resetCount

    public void resetCount()

  Resets the step counter to 0. This method is called at the start of all heap operations. After executing the operation, use `getCount()` to get the time complexity of that operation (see class intro for more details).

### getKeyColorMode

    public static boolean getKeyColorMode()

  Returns:
    TRUE iff 'key color' mode is active

### setKeyColorMode

    public static void setKeyColorMode(boolean b)

  Sets the 'key color' mode. In this mode, the fill color of each node relfects that node's key value.

  Parameters:
    `b` - TRUE iff 'key color' is on

### setTextMode

    public static void setTextMode(int mode)

  Sets the 'text mode' to accompany operations by text. Possible values are: NONE, NORMAL, DETAIL

  Parameters:
    `mode` - the text mode

### maxRank

    public int maxRank()

  Returns the maximum possible rank of a node in this `FibHeap`. This number is in O(log n) where n is the heap size.

  Returns:
    maximum possible rank of a node

### getMainCompObj

    public jedas.CompObj getMainCompObj()

  Description copied from interface: `JedasMainCompObj`
  Returns the main CompObj which to visualize in the JEDAS animation-area.

  Specified by:
    `getMainCompObj` in interface `JedasMainCompObj`
  Returns:
    CompObj to view in JEDAS-animation-panel

### getSubOperationQueue

    public SubOperationQueue getSubOperationQueue()

### add

    public void add(SubOperation so)

### clearSubOperationQueue

    public void clearSubOperationQueue()

### deepCopy

    public java.lang.Object deepCopy()

  Description copied from interface: `Copyable`
  Performs a deep copy of the implemented data-structure

  Specified by:
    `deepCopy` in interface `Copyable`
  Returns:
    copy of the data-structure

### copy

    public java.lang.Object copy()

### toString

    public java.lang.String toString()

  Overrides:
    `toString` in class `java.lang.Object`

### copyDS

    public java.lang.Object copyDS()

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD