Package cpsc331.collections

Interface MinHeap<T extends java.lang.Comparable<T>>

public interface MinHeap<T extends java.lang.Comparable<T>>

Provides an interface for an unbounded binary MinHeap

MinHeap Invariant: A finite multiset of values of ordered type T is stored in a binary MinHeap

Method Summary

Modifier and Type	Method	Description
T	deleteMin()
int	getSize()
void	insert(T v)

Method Detail

insert

void insert(T v)

Parameters:

v - the value to be inserted into this binary MinHeap

Precondition:

1. The MinHeap Invariant is satisfied.
2. A value v with type T has been given as input.

Postcondition:

1. The MinHeap Invariant is satisfied.
2. A copy of the value v has been inserted into the multiset represented by this binary MinHeap. No other changes have been made.

deleteMin

T deleteMin()
     throws java.util.NoSuchElementException

Returns:

the value that was deleted from this MinHeap

Throws:

java.util.NoSuchElementException - if this MinHeap was already empty

Precondition:

1. The MinHeap Invariant is satisfied.

Postcondition:

1. The MinHeap Invariant is satisfied.
2. If this MinHeap was not empty then a copy of the smallest element is removed from the multiset represented by this MinHeap and returned as output, and no other changes to this multiset have been made. A NoSuChElementException is thrown if this heap was already empty, an it is not changed.

getSize

int getSize()

Returns:

the current size of this MinHeap

Precondition:

1. The MinHeap Invariant is satisfied.

Postcondition:

1. This MinHeap has not changed, so the MinHeap Invariant is still satisfied.
2. The size of this MinHeap has been returned as output.