org.basex.util

Class MinHeap<K,V>

java.lang.Object

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:

Leo Woerteler

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
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