C++ Data Structures and Algorithms

Inserting a new element into the heap

A new element will be inserted in the last vector. However, we need to shift the element up to ensure that it will be in the right place based on the value of the element. To do so, we need to create the ShiftUp() operation, which will swap two adjacent elements so that the vector will be in order. The implementation of the ShiftUp() operation will be as follows:

    void BinaryHeap::ShiftUp(int index)    {        // Do nothing in root        if (index == 1)            return;        if (vect[index] > vect[p(index)])        {            // Swap Upwards            std::swap(vect[index], vect[p(index)]);            // Recurse until root            ShiftUp(p(index));        }    }

After we have the ShiftUp() operation, we can create the Insert() operation as follows:

void BinaryHeap::Insert(int key)