structure
Interface MergeableHeap

All Superinterfaces:

PriorityQueue

All Known Implementing Classes:

SkewHeap

public interface MergeableHeap

extends PriorityQueue

Interface describing mergeable min heaps. Min heaps are collections of Comparable data that guarantee efficient access to the smallest element in the structure. Mergeable Min heaps, also provide an efficient technique for merging two mergeable heaps of the same type. Mergeable heaps are quite similar to PriorityQueue.

Example Usage:

 public static void main(String[] argv){
	//initialize a new fib heap
	MergeableHeap programmers = new FibHeap();

	//add programmers and their ages to heap
	//ages current of 7/22/2002
        programmers.add(new ComparableAssociation(new Integer(22), "Evan"));
	programmers.add(new ComparableAssociation(new Integer(19), "Chris"));
	programmers.add(new ComparableAssociation(new Integer(20), "Shimon"));
	programmers.add(new ComparableAssociation(new Integer(21), "Diane"));
	programmers.add(new ComparableAssociation(new Integer(21), "Lida"));	
	programmers.add(new ComparableAssociation(new Integer(20), "Rob"));	
	programmers.add(new ComparableAssociation(new Integer(20), "Sean"));	

	//print out programmers 
	while(!programmers.PriorityQueue.isEmpty()){
	    ComparableAssociation p = (ComparableAssociation)programmers.remove();
	    System.out.println(p.getValue() + " is " + p.getKey() + " years old.");
	}
 }
 

Method Summary

void	add(Comparable value) Add an item to this heap.
Comparable	getFirst() Return the minimum value in the heap.
void	merge(MergeableHeap otherHeap) Merge this heap with otherHeap, destroying otherHeap in the process.
Comparable	remove() Returns the minimum value in the heap and deletes this value from the heap.

Methods inherited from interface structure.PriorityQueue

clear, isEmpty, size

Method Detail

merge

public void merge(MergeableHeap otherHeap)

Merge this heap with otherHeap, destroying otherHeap in the process.

Parameters:

otherHeap - Heap to be merged into this heap.

Postcondition:

This heap contains all of the elements formerly contained by otherHeap. otherHeap is destroyed in in the process.

add

public void add(Comparable value)

Add an item to this heap.

Specified by:

add in interface PriorityQueue

Parameters:

value - The value to be added to the heap

Precondition:

value is non-null

Postcondition:

value is added to the heap.

remove

public Comparable remove()

Returns the minimum value in the heap and deletes this value from the heap.

Specified by:

remove in interface PriorityQueue

Postcondition:

Heap no longer contains the minimum value.

Returns:

The minumum value in the heap, or null if the heap is empty.

getFirst

public Comparable getFirst()

Return the minimum value in the heap.

Specified by:

getFirst in interface PriorityQueue

Postcondition:

The minimum value is returned.

Returns:

The minimum value in the heap.