cpsc331.collections

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

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

Provides an interface for an bounded binary MinHeap

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

Method Summary

Modifier and Type	Method and Description
T	deleteMin()
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 MinHeap

Throws:

HeapFullException - if this bounded MinHeap is already full

Precondition:

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

Postcondition:

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

deleteMin

T deleteMin()
     throws java.util.NoSuchElementException

Returns:

the value that was deleted from this BoundedMinHeap

Throws:

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

Precondition:

1. The MinHeap Invariant is satisfied.

Postcondition:

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

Postcondition:

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

getCapacity

int getCapacity()

Returns:

the capacity of this BoundedMaxHeap
Precondition:

1. The BoundedMinHeap Invariant is satisfied.

Postcondition:

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