com.flat502.rox.utils
Class MinHeap

java.lang.Object
  com.flat502.rox.utils.MinHeap

public class MinHeap
extends java.lang.Object

A minimum binary heap implementation.

This heap implementation is keyed on long values. It provides O(log n) inserts, O(C) remove minumum element, O(N) remove arbitary element.

This implementation is unsynchronized. Concurrent access from multiple threads should be controlled by the caller.

Constructor Summary

MinHeap()
Constructs a new MinimumBinaryHeap instance with an initial size of 10 and a growth increment of 10.

MinHeap(int initial_size)
Constructs a new MinimumBinaryHeap instance the specified initial size and a growth increment of 10.

MinHeap(int initial_size, int growth_step)
Constructs a new MinimumBinaryHeap instance the specified initial size and growth increment

Method Summary

void	clear()
java.lang.Object	getSmallest()
void	insert(long key, java.lang.Object value)
void	insertUnordered(long key, java.lang.Object value)
boolean	isEmpty()
static void	main(java.lang.String[] args)
void	removeKey(long key)
java.lang.Object	removeSmallest()
void	removeValue(java.lang.Object value) This method makes use of the equals() method to locate entries in the heap that are to be removed.
int	size()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinHeap

public MinHeap()

Constructs a new MinimumBinaryHeap instance with an initial size of 10 and a growth increment of 10.

MinHeap

public MinHeap(int initial_size)

Constructs a new MinimumBinaryHeap instance the specified initial size and a growth increment of 10.

Parameters:

initial_size - The initial size of the heap.

MinHeap

public MinHeap(int initial_size,
               int growth_step)

Constructs a new MinimumBinaryHeap instance the specified initial size and growth increment

Parameters:

initial_size - The initial size of the heap.

growth_step - The growth increment to use.

Method Detail

isEmpty

public boolean isEmpty()

Returns:

true if the heap is empty, false if not.

size

public int size()

Returns:

The number of elements stored in the heap.

insert

public void insert(long key,
                   java.lang.Object value)

insertUnordered

public void insertUnordered(long key,
                            java.lang.Object value)

getSmallest

public java.lang.Object getSmallest()

removeSmallest

public java.lang.Object removeSmallest()

removeKey

public void removeKey(long key)

removeValue

public void removeValue(java.lang.Object value)

This method makes use of the equals() method to locate entries in the heap that are to be removed.

This method does not reorder the heap

clear

public void clear()

main

public static void main(java.lang.String[] args)