class Heap
{
private:

    // The heap array itself.
    int *heap_array;

    // The size of the heap array (may be larger than the heap size).
    int array_size;

    // The current number of elements in the heap.
    int heap_size;

    // How much to grow the heap array when it becomes full.
    int inc_size;


    // Heapify the array at the passed index.
    void Heapify( int *array, int index, int size );

    // Build a heap from the heap array.
    void BuildHeap();


public:

    // Constructor that creates an empty heap with a specified initial
    // size (capacity) and increment size.
    Heap( int initial_size, int increment_size );

    // Constructor that creates a heap from the passed array with a
    // specified increment size.
    Heap( int *array, int size, int increment_size );

    // Inserts a new value into the heap.
    void Insert( int new_value );

    // Extracts the maximum value from the heap.
    int ExtractMax();

    // Returns the maximum value from the heap (without extracting it).
    int Max();

    // Returns a sorted array of the values in the heap array.
    int *HeapSort( int &size ); 
};