cpsc331.collections

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

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

Provides an interface for an unbounded binary MaxHeap

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

Method Summary

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

Method Detail

insert

void insert(T v)

Parameters:

v - the value to be inserted into this binary MaxHeap

Precondition:

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

Postcondition:

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

deleteMax

T deleteMax()
     throws java.util.NoSuchElementException

Returns:

the value that was deleted from this MaxHeap

Throws:

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

Precondition:

1. The MaxHeap Invariant is satisfied.

Postcondition:

1. The MaxHeap Invariant is satisfied.
2. If this MinHeap was not empty then a copy of the largest element is removed from the multiset represented by this MaxHeap 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 MaxHeap

Precondition:

1. The MaxHeap Invariant is satisfied.

Postcondition:

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