Requirements

In this sub-project, you will implement one class:

A binary min-heap: QuaternaryMinHeap

Description

This class stores a fixed number of values in a binary minimum heap. If there are zero elements in the heap, the heap is said to be empty. The constructor is passed the capacity as an argument (defaulting to 10). The heap is to be implemented as is desribed in the course notes.

Member Variables

Use whatever member variables you feel are necessary.

Member Functions

Constructors

BinaryMinHeap( int = 10 )

This allocates enough memory for a heap capable of storing n objects.

Destructor

Any memory you allocated must be cleaned up. (O(1))

Copy Constructor

Create a copy of the object. (O(1))

Assignment Operator `=`

Assign the heap to be an exact copy, in all respects, of the argument. (O(n_rhs))

Accessors

This class has seven accessors:

int size() const;: Returns the number of items in the heap. (O(1))
int capacity() const;: Returns the number of items which can be stored in the heap. (O(1))
bool empty() const;: Returns true if the heap is empty, false otherwise. (O(1))
bool full() const;: Returns true if the heap is full, false otherwise. (O(1))
Type head() const;: Retrieves the object stored in the front of the heap. This function throws a underflow if the heap is empty. (O(1))
Type retrieve( int n ) const;: Returns the object stored in the nth location of the array implementation of the heap. The argument will always be between 1 and size(). O(1)
bool member( Type const & ) const;: Returns true if the argument is stored in the heap and false otherwise. (O(n))

Mutators

This class has four mutators:

void push_heap( Type const & );: This places the argument into the appropriate location in the heap as per the course notes and moves it up the heap as necessary. If the heap is full, throw an overflow exception. (O(ln(n)))
Type pop_heap();: Dequeue the minimum element from the heap and return it. The heap must be modified as described in course notes. Be sure to keep track of the last element in the array. (O(ln(n)))
bool remove( Type const & );: Remove the argument from the heap. You will have to perform a similar operation to pop_heap(), however, you will start at the location in the array where the object is removed. (O(n))
void clear();: Make the heap empty. (O(1)

Quaternary heap