//Se considera urmatoarea secventa de valori:
//
//17 34 51 68 85 2 19 36 53 70 87 4 21 38 55 72 89 6 23 40 57 74 91 8 25 42 59 76 93 10 27 44
//61 78 95 12 29 46 63 80 97 14 31 48 65 82 16 33 50 67 84 1 18 35 52 69 86 3 20 37 54 71 88 5
//22 39 56 73 90 7 24 41 58 75 92 9 26 43 60 77 94 11 28 45 62 79 96 13 30 47 64 81 15 32 49 83
//
//
//
//------------------------------------
//A. Restantieri seria 2019-2020
//------------------------------------
//
//Sa se construiasca o structura max-heap cu urmatoarele valori:
//
//1) afisati primele 5 valori ale structurii de date heap
//
//2) afisati toate elementele de pe nivelul 3 (radacina este nivelul 0)
//
//3) Sortati aceste elemente cu algoritmul HeapSort


// C++ program for implementation of Heap Sort
#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// main function to do heap sort
void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

/* A utility function to print array of size n */
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

int main() {
    int arr[] = {17, 34, 51, 68, 85, 2, 19, 36, 53, 70, 87, 4, 21, 38, 55, 72, 89, 6, 23, 40, 57, 74, 91, 8, 25, 42, 59,
                 76, 93, 10, 27, 44,
                 61, 78, 95, 12, 29, 46, 63, 80, 97, 14, 31, 48, 65, 82, 16, 33, 50, 67, 84, 1, 18, 35, 52, 69, 86, 3,
                 20, 37, 54, 71, 88, 5,
                 22, 39, 56, 73, 90, 7, 24, 41, 58, 75, 92, 9, 26, 43, 60, 77, 94, 11, 28, 45, 62, 79, 96, 13, 30, 47,
                 64, 81, 15, 32, 49, 83};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "n=" << n << "\n";

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    cout<<"Max-heap: ";
    printArray(arr, n);
    cout<<endl;
    cout << "Primele 5 elemente: ";
    printArray(arr, 5);
    cout << endl;
    cout << "Elementele de pe al 3-lea nivel sunt: ";
    for (int i = 7; i <= 14; i++)cout << arr[i] << " ";
    cout<<endl;
    heapSort(arr, n);
    cout << "Max-heap sorted: ";
    printArray(arr, n);

}