//HEAP
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

class Heap {
private:
    vector<int> data;

    int getLeft(int pos) {
        return (pos * 2) + 1;
    }

    int getRight(int pos) {
        return (pos * 2) + 2;
    }

    int getParent(int pos) {
        return (pos - 1) / 2;
    }

    void siftUp(int pos) {
        int parent = getParent(pos);
        while (data[pos] > data[parent]) {
            swap(data[pos], data[parent]);
            if (parent <= 0) {
                return;
            }
            parent = getParent(parent);
            pos = getParent(pos);
        }
    }

    void siftDown(int pos) {
        bool hasRight = getRight(pos) < data.size();
        bool hasLeft = getLeft(pos) < data.size();

        if (hasRight && (data[pos] < data[getLeft(pos)] || data[pos] < data[getRight(pos)])) {
            int swapWith = -1;
            if (data[getLeft(pos)] < data[getRight(pos)]) {
                swapWith = getRight(pos);
            } else {
                swapWith = getLeft(pos);
            }

            swap(data[pos], data[swapWith]);
            siftDown(swapWith);
        }
        else if (hasLeft && data[pos] < data[getLeft(pos)]) {
            swap(data[pos], data[getLeft(pos)]);
            siftDown(getLeft(pos));
        }
    }

public:
    bool isEmpty() const {
        return data.size() == 0;
    }
    void add(int number) {
        data.push_back(number);
        if (data.size() != 0) {
            siftUp(data.size() - 1);
        }
    }

    int peekTop() {
        return data[0];
    }

    void popTop() {
        if (isEmpty()) {
            return;
        }

        swap(data[0], data[data.size() - 1]);
        data.pop_back();
        siftDown(0);
    }
};

//Levelorder BFS
void levelorder() const {
        queue<Node*> que;
        que.push(root);

        while(!que.empty()) {
            Node* current = que.front();
            que.pop();
            if (current) {
                cout << current->data << " ";

                if (current->left) {
                    que.push(current->left);
                }
                if (current->right) {
                    que.push(current->right);
                }
            }
        }
    }



//Depth first search
 void _inorder(Node* current) const {
        if (current) {
            _inorder(current->left);
            cout << current->data << " ";
            _inorder(current->right);
        }
    }

    void _preorder(Node* current) const {
        if (current) {
            cout << current->data << " ";
            _preorder(current->left);
            _preorder(current->right);
        }
    }

    void _postorder(Node* current) const {
        if (current) {
            _postorder(current->left);
            _postorder(current->right);
            cout << current->data << " ";
        }
    }


//HEAPIFY
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);
    }
}