scranton.tree
Interface Heap

All Known Implementing Classes:

HeapViaArray

public interface Heap

Heap interface, assume a comparator applies the heap order. The class includes several utilities fall into two categories 1. Methods to support the heap-to-array relationship and the corresponding index calculations 2. The code for the siftUp and siftDown methods

Method Summary

void	insert(java.lang.Object val) Method insert a new object and reorganize the heap by applying the siftUp process.
java.lang.Object	remove() Method removes the root and applies the heap siftDown process to maintain the heap correctly.
int	size() Method size reports the current size of the heap.

Method Detail

size

public int size()

Method size reports the current size of the heap.

Returns:

int Returns the size of the heap

insert

public void insert(java.lang.Object val)

Method insert a new object and reorganize the heap by applying the siftUp process. The method should have timing, O(log(n)), where n is the number of objects in the heap

Parameters:

val -

remove

public java.lang.Object remove()

Method removes the root and applies the heap siftDown process to maintain the heap correctly. The method should have timing, O(log(n)), where n is the number of objects in the heap

Returns:

Object - the root of the heap