heap#8

#include <iostream>
using namespace std;

// Function to maintain the max-heap property
void maxHeapify(int heap[], int n, int i) {
int largest = i; // Assume the largest is the current index
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index

// Check if left child exists and is greater than the current largest
if (left < n && heap[left] > heap[largest]) {
    largest = left;
}

// Check if right child exists and is greater than the current largest
if (right < n && heap[right] > heap[largest]) {
    largest = right;
}

// If the largest is not the current element, swap and recursively heapify
if (largest != i) {
    swap(heap[i], heap[largest]);
    maxHeapify(heap, n, largest);
}

}

// Function to build the max-heap from the given array
void buildMaxHeap(int heap[], int n) {
// Start from the last non-leaf node and call maxHeapify
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(heap, n, i);
}
}

// Function to insert a new score into the max-heap
void insertHeap(int heap[], int& n, int value) {
// Insert the new element at the end
heap[n] = value;
n++; // Increment the size of the heap

// Call maxHeapify-up to ensure the heap property is maintained
buildMaxHeap(heap,n);

}

// Function to display the elements of the heap
void displayHeap(int heap[], int n) {
for (int i = 0; i < n; i++) {
cout << heap[i] << " ";
}
cout << endl;
}

int main() {
int n;
cin >> n;

int heap[16]; // Array to hold the heap (size n + 1)

// Read the initial scores and build the max heap
for (int i = 0; i < n; i++) {
    cin >> heap[i];
}

// Build the max-heap
buildMaxHeap(heap, n);

// Read the new score to be inserted
int newScore;
cin >> newScore;

// Insert the new score into the heap
insertHeap(heap, n, newScore);

// Display the updated heap
displayHeap(heap, n);

return 0;

}