How to perform Insertion in Binary Sort?

Software Development
#1

Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element into the Heap maintaining the properties of the Heap.

When we consider insertion in a max heap -

  • First increase the heap size by 1, so that it can store the new element.
  • Insert the new element at the end of the Heap.
  • This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

Time complexity is O(log N) since in the worst case we need to travel all the way to the root item.

 void insert(int data) {
        if (size >= MAX_SIZE) {
            cout<<"The heap is full. Cannot insert"<<endl;
            return;
        }

        heap[size] = data;
        size = size + 1;

        int i = size - 1;
        while (i != 0 && heap[BinaryHeap::parent(i)] < heap[i]) {
            BinaryHeap::swap(&heap[BinaryHeap::parent(i)], &heap[i]);
            i = BinaryHeap::parent(i);
        }
    }