Insert in Binary Heap

Problem Statement: Given a Binary Heap, Insert the new value in the Binary Heap.

Solution :

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Steps Followed for inserting the key in Binary Heap:

First Insert the key at the first vacant position from the left on the last level of the heap. IF the last level is completely filled, then insert the key as the left-most element in the next level.
Inserting a new key at the first vacant position in the last level preserves the Complete binary tree property, The Min heap property may get affected we need to check for it.
If the inserted key parent is less than the key, then the Min heap property is also not violated.
If the parent is greater than the inserted key value, then swap the values. Now the heap property may get violated at the parent node. So repeat the same process until the heap property is satisfied.
Inserting an element takes O(logN) Time Complexity. Below shows the animation of how -1 is inserted into a Binary heap by following above described steps.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class BinaryHeap {
  public:
    int capacity; /*Maximum elements that can be stored in heap*/
  int size; /*Current no of elements in heap*/
  int * arr; /*array for storing the keys*/

  BinaryHeap(int cap) {
    capacity = cap; /*Assigning the capacity*/
    size = 0; /*Intailly size of hepa is zero*/
    arr = new int[capacity]; /*Creating a array*/
  }

  /*returns the parent of ith Node*/
  int parent(int i) {
    return (i - 1) / 2;
  }
  /*returns the left child of ith Node*/
  int left(int i) {
    return 2 * i + 1;
  }
  /*Returns the right child of the ith Node*/
  int right(int i) {
    return 2 * i + 2;
  }

  /*Insert a new key x*/
  void Insert(int x) {
    if (size == capacity) {
      cout << "Binary Heap Overflwon" << endl;
      return;
    }
    arr[size] = x; /*Insert new element at end*/
    int k = size; /*store the index ,for checking heap property*/
    size++; /*Increase the size*/

    /*Fix the min heap property*/
    while (k != 0 && arr[parent(k)] > arr[k]) {
      swap( & arr[parent(k)], & arr[k]);
      k = parent(k);
    }
  }

  int getMin() {
    return arr[0];
  }

  void swap(int * x, int * y) {
    int temp = * x;
    * x = * y;
    * y = temp;
  }
};
int main()

{
  BinaryHeap h(20);
  h.Insert(4);
  h.Insert(1);
  h.Insert(2);
  h.Insert(6);
  h.Insert(7);
  h.Insert(3);
  h.Insert(8);
  h.Insert(5);
  cout << "Min value is " << h.getMin() << endl;
  h.Insert(-1);
  cout << "Min value is " << h.getMin() << endl;
  return 0;
}

Output:

Min value is 1
Min value is -1

Time Complexity : O(logN)

Java Code

import java.util.*;

class BinaryHeap {
  static int capacity; /*Maximum elements that can be stored in heap*/
  static int size; /*Current no of elements in heap*/
  static int arr[]; /*array for storing the keys*/

  BinaryHeap(int cap) {
    capacity = cap; /*Assigning the capacity*/
    size = 0; /*Intailly size of hepa is zero*/
    arr = new int[capacity]; /*Creating a array*/
  }

  /*returns the parent of ith Node*/
  static int parent(int i) {
    return (i - 1) / 2;
  }
  /*returns the left child of ith Node*/
  static int left(int i) {
    return 2 * i + 1;
  }
  /*Returns the right child of the ith Node*/
  static int right(int i) {
    return 2 * i + 2;
  }

  /*Insert a new key x*/
  static void Insert(int x) {
    if (size == capacity) {
      System.out.println("Binary Heap Overflown");
      return;
    }
    arr[size] = x; /*Insert new element at end*/
    int k = size; /*store the index ,for checking heap property*/
    size++; /*Increase the size*/

    /*Fix the min heap property*/
    while (k != 0 && arr[parent(k)] > arr[k]) {
      int temp = arr[parent(k)];
      arr[parent(k)] = arr[k];
      arr[k] = temp;
      k = parent(k);
    }
  }

  static int getMin() {
    return arr[0];
  }

  public static void main(String args[])

  {
    BinaryHeap h = new BinaryHeap(20);
    h.Insert(4);
    h.Insert(1);
    h.Insert(2);
    h.Insert(6);
    h.Insert(7);
    h.Insert(3);
    h.Insert(8);
    h.Insert(5);
    System.out.println("Min value is " + h.getMin());
    h.Insert(-1);
    System.out.println("Min value is " + h.getMin());

  }
}

Output:

Min value is 1
Min value is -1

Time Complexity : O(logN)

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article