Heap Insert

class MaxHeap {
    vector<int> heap;

public:
    void push(int val) {
        // Step 1: append new value to the end of the array
        heap.push_back(val);
        int i = heap.size() - 1;

        // Step 2: bubble up — compare with parent
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] <= heap[parent]) break;   // heap property satisfied

            // Step 3: swap with parent and move up
            swap(heap[i], heap[parent]);
            i = parent;
        }
    }
};