Задача на C++. Пирамидальная сортировка

[Mikdon]

Реализовать пирамидальную сортировку(сортировку кучей)
Дается заголовочный файл в котором прописаны все условия.
Время до 7:00 по МСК. Оплата 500 рублей (ЯД, WM, Сбербанк.Онлайн)
e-mail для связи: ilyasanguinum@yandex.ru

/**
 * The current assessment is to implement Heap Sort algorithm and the Heap datastructure itself.
 * The idea might seem a bit not clear for the first time, but spend some time on
 * understanding the fundamentals of the algorithm. After you really understand how
 * the algorithm works, it will be really easy to implement all methods that are
 * presented here.
 *
 * The only file that you need to upload for the assessment is heap_sort.cpp - your
 * implementation for current header file.
 *
 * YOU MUST NOT MODIFY CURRENT FILE!!!
 *
 * You should consider the following descriptions of the methods and find out
 * how they should interact with each other.
 *
 * Then you need to create heap_sort.cpp file and implement all declared functions from here.
 *
 * If you need some additional functions to implement - be free to add them to your heap_sort.cpp
 * file (not heap_sort.h file!). In fact, that will be appreciated if it is used properly.
 *
 * Your heap_sort.cpp file MUST be compatible with this version of current file. So, again:
 * YOU MUST NOT MODIFY CURRENT FILE!!!
 *
 * All methods should be implemented and all of them should be used in your work.
 *
 * You should consider that all methods should work in isolation and all of them MUST NOT affect any
 * system state (i.e. static fields and so on).
 *
 * Don't provide any "int main()" method in your heap_sort.cpp file. You can create it for self
 * testing in another separate file.
 *
 * Don't forget about comments and good coding style, which will be appreciated.
 *
 * NOTE: There are some disclaimers in comments about possible values that are passed to the methods.
 * These comments like "Non-negative integer value" or "Strictly positive integer value" are just
 * some hints for you to be aware of possible values that can be passed to your method.
 * In other words, if there is a comment that the input parameter is strictly positive we will not
 * test that method with negative values of this parameter so you don't need to consider such cases.
 * In practice, such comments are widely used in API design where you do not guarantee correct behavior
 * in case of wrong parameters (which would be a nonsense if you do).
 */

/*
 * Class to have a function of sorting.
 */
class Heapsort {
public:
    /*
     * The Heap sort algorithm. The algorithm should sort the array that is passed
     * as a parameter of the function in non-decreasing order.
     *
     * In this function you need to create an instance of the "Heap" class and use it for sorting.
     * Then, if you allocated memory in Heap, you need properly deallocate that memory.
     *
     * KEY HINT: in this case, sort is not meant to be in place.
     * So we assume here that you are going to use some extra memory
     * for Heap data structure itself while heapSort method is processing.
     *
     * Parameters:
     *  int *arr - array to sort.
     *  int n    - size of the array.
     */
    static void heapSort(int *arr, int n);
};

/**
 * Class that represents simplified heap data structure.
 *
 * Current heap type is dedicated to extract THE SMALLEST value
 * from the heap.
 *
 * So every parent element has value less or equal than child elements.
 * This state is referred as "heap" state later in current file.
 *
 * So, you need to figure it out, how you can simply use such heap
 * type in assistance of sorting.
 *
 */
class Heap {
// commented for testing
//private:
public:
    /**
     * Inner values in the heap are stored in this array. This array should
     * have proper "heap" state between any calls of the public functions.
     *
     * In other words, if somebody calls any public functions of this class
     * (except destructor) then the array should have values in such order,
     * that is used in heap data structure in array implementation.
     */
    int *storage;

    /** Number of elements that are currently in current instance of heap */
    int currentSize;

    /**
     * Number of elements that can be stored in current instance of heap.
     * The value should be once initialized in constructor and never change
     * its value.
     */
    const int capacity;

public:
    /**
     * Constructor method of the heap.
     *
     * Parameters:
     *  int *source - array that is need to be stored in heap. The passed array
     *                can be in any order (sorted or not).
     *  int n       - number of elements in passed array. ALSO this value should
     *                be used as a capacity of the current heap instance.
     *
     * Also, this is IMPORTANT not to modify the array that is passes as a parameter.
     * That doesn't mean that you should store that array in such way that is passed,
     * but to copy it to the internal storage.
     */
    Heap(const int *source, const int n);

    /**
     * Destructor of the heap. Don't forget to clean all allocated memory here.
     */
    ~Heap();

    /**
     * Getting the minimum value from the heap. This method doesn't change state of
     * the heap.
     *
     * Complexity: O(1)
     */
    int getMin();

    /**
     * Getting the minimum value from the heap and also extracting it from the heap.
     * After this function, the heap should be modified and be in proper "heap" state.
     *
     * If heap currently has 0 elements stored, then the std::length_error exception
     * should be thrown with informative message.
     *
     * Complexity: O(log(current_size))
     *
     * Returns:
     *  minimum value that is in the heap.
     */
    int extractMin();

    /**
     * Inserting the value in the heap.
     * After this function, the heap should be modified and be in proper "heap" state.
     *
     * If heap currently has "capacity" elements stored, then the std::length_error exception
     * should be thrown with informative message.
     *
     * Complexity: O(log(current_size + 1))
     */
    void insert(const int value);

    // commented for testing
//private:
    /**
     * Method to perform heapify operation to the specified element in terms of checking
     * the "heap" state for it children's values. In other words we need to "bubble-down"
     * the specified element swapping it with one of the child nodes if necessary. After the
     * function execution, the heap storage should be in proper "heap" state (children nodes
     * are equal or greater than parent node).
     *
     * Hint: this method should be used in "extract_min" function.
     *
     * Complexity: O(log(current_size))
     */
    void heapifyDown(int index);

    /**
     * Method to perform heapify operation to the specified element in terms of checking
     * the "heap" state for it parent's values. In other words we need to "bubble-up"
     * the specified element swapping it with parent node if necessary. After the
     * function execution, the heap storage should be in proper "heap" state (children nodes
     * are equal or greater than parent node).
     *
     * Hint: this method should be used in "insert" function.
     *
     * Complexity: O(log(current_size))
     */
    void heapifyUp(int index);
};