1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Function to swap two elements
6void swap(int& a, int& b) {
7    int temp = a;
8    a = b;
9    b = temp;
10}
11
12// Function to max heapify the subtree with root at given index
13void maxHeapify(vector<int>& arr, int n, int i) {
14    int largest = i; // Initialize the largest element as root
15    int left = 2 * i + 1; // Left child
16    int right = 2 * i + 2; // Right child
17
18    // If left child is larger than root
19    if (left < n && arr[left] > arr[largest])
20        largest = left;
21
22    // If right child is larger than largest so far
23    if (right < n && arr[right] > arr[largest])
24        largest = right;
25
26    // If largest is not root
27    if (largest != i) {
28        swap(arr[i], arr[largest]);
29
30        // Recursively heapify the affected sub-tree
31        maxHeapify(arr, n, largest);
32    }
33}
34
35// Function to convert an array to max heap
36void buildMaxHeap(vector<int>& arr, int n) {
37    // Index of last non-leaf node
38    int startIdx = (n / 2) - 1;
39
40    // Perform max heapify on each non-leaf node
41    // From right to left
42    for (int i = startIdx; i >= 0; i--) {
43        maxHeapify(arr, n, i);
44    }
45}
46
47// Function to print an array
48void printArray(vector<int>& arr, int n) {
49    for (int i = 0; i < n; i++) {
50        cout << arr[i] << " ";
51    }
52    cout << endl;
53}
54
55int main() {
56    vector<int> arr = { 12, 11, 13, 5, 6, 7 };
57    int n = arr.size();
58
59    cout << "Original array: ";
60    printArray(arr, n);
61
62    buildMaxHeap(arr, n);
63
64    cout << "Max Heap: ";
65    printArray(arr, n);
66
67    return 0;
68}