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)
