org.basex.util
Class MinHeap<K,V>

java.lang.Object
  extended by org.basex.util.MinHeap<K,V>
Type Parameters:
K - key type
V - value type

public final class MinHeap<K,V>
extends java.lang.Object

A min-heap.

Author:
BaseX Team 2005-12, BSD License, Leo Woerteler

Constructor Summary
MinHeap(int cap, java.util.Comparator<K> cmp)
          Constructs a heap with the given initial capacity and order.
 
Method Summary
 void insert(K key, V value)
          Inserts the given key/value pair into the heap.
 boolean isEmpty()
          Checks if this heap is empty.
 V minValue()
          returns the value of the smallest key from this heap.
 V removeMin()
          Removes the minimum from this heap.
 int size()
          Size of this heap.
 java.lang.String toString()
           
 void verify()
          Verifies the inner structure of the heap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

MinHeap

public MinHeap(int cap,
               java.util.Comparator<K> cmp)
Constructs a heap with the given initial capacity and order.

Parameters:
cap - initial capacity
cmp - comparator
Method Detail

insert

public void insert(K key,
                   V value)
Inserts the given key/value pair into the heap.

Parameters:
key - key
value - value

removeMin

public V removeMin()
Removes the minimum from this heap.

Returns:
the removed entry's value

minValue

public V minValue()
returns the value of the smallest key from this heap.

Returns:
value of the smallest key

size

public int size()
Size of this heap.

Returns:
number of entries

isEmpty

public boolean isEmpty()
Checks if this heap is empty.

Returns:
true if heap is empty, false otherwise

verify

public void verify()
Verifies the inner structure of the heap.

Throws:
java.lang.IllegalStateException - if the invariants don't hold

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object