cpsc331.collections

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

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

Provides an interface for an bounded binary MaxHeap

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

Method Summary

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

Method Detail

insert

void insert(T v)
     throws HeapFullException

Parameters:

v - the value to be inserted into this binary MaxHeap

Throws:

HeapFullException - if this bounded MaxHeap is already full

Precondition:

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

Postcondition:

1. The BoundedMaxHeap Invariant is satisfied.
2. If this BoundedMaxHeap is not already full then a copy of the value v has been inserted into the multiset represented by this binary MaxHeap, and no other changes have been made. A HeapFullException is thrown, and this bounded MaxHeap is not changed, otherwise.

deleteMax

T deleteMax()
     throws java.util.NoSuchElementException

Returns:

the value that was deleted from this BoundedMaxHeap

Throws:

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

Precondition:

1. The BoundedMaxHeap 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 BoundedMaxHeap Invariant is satisfied.

Postcondition:

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

getCapacity

int getCapacity()

Returns:

the capacity of this BoundedMaxHeap

Precondition:

1. The BoundedMaxHeap Invariant is satisfied.

Postcondition:

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