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 FibHeapDS

    java.lang.Object
      mauda.plugin.fibheap.FibHeapDS

Direct Known Subclasses:
  FibHeapDSExt

    public class FibHeapDS

extends java.lang.Object

A fast-class for operations of FibHeaps

Author:
  Markus Krebs

Field Summary
`java.util.IdentityHashMap` | `fibNodes`
`static SubOperationQueue` | `subOperations`

Constructor Summary
`FibHeapDS()` 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` | `clone()`
`void` | `decreasekey(FibNodeDS N, int k)` Decreases the key of the specified node to the specified value.
`int` | `delete(FibNodeDS 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()`
`SubOperationQueue` | `getSubOperationQueue()`
`FibNodeDS` | `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(FibHeapDS other)` Melds another `FibHeap` into this one.
`void` | `resetCount()` Resets the step counter to 0.

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

Field Detail

### subOperations

    public static SubOperationQueue subOperations

### fibNodes

    public java.util.IdentityHashMap fibNodes

Constructor Detail

### FibHeapDS

    public FibHeapDS()

  Creates a new, empty FibHeap.

Method Detail

### isEmpty

    public boolean isEmpty()

  Returns:
    true if this `FibHeap` is empty

### meld

    public void meld(FibHeapDS 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 FibNodeDS 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(FibNodeDS 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(FibNodeDS 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).

### 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

### getSubOperationQueue

    public SubOperationQueue getSubOperationQueue()

### add

    public void add(SubOperation so)

### clearSubOperationQueue

    public void clearSubOperationQueue()

### clone

    public java.lang.Object clone()

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

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