Insertion in Heap

In the context of the heap data structure, insertion refers to the process of adding a new element to the heap while maintaining the heap property.

When inserting an element into a min heap, the new element is placed at the next available position in the heap array. The heap property is then restored by comparing the new element with its parent and swapping them if necessary until the heap property is satisfied.

Here is an example Java implementation of the insert(value) method in a MinHeap class:

1class MinHeap {
2  private int[] heapArray;
3  private int maxSize;
4  private int heapSize;
5
6  public MinHeap(int size) {
7    maxSize = size;
8    heapSize = 0;
9    heapArray = new int[maxSize];
10  }
11
12  public void insert(int value) {
13    if (isFull()) {
14      System.out.println("Heap is full. Cannot insert.");
15    } else {
16      heapArray[heapSize] = value;
17      heapSize++;
18      heapifyUp(heapSize - 1);
19    }
20  }
21
22  // Other methods...
23}

In the example code, we have a MinHeap class with an array heapArray to store the elements. The insert(value) method takes a value as input and checks if the heap is full. If the heap is not full, the new element is placed at the next available position in the array (heapSize) and heapifyUp() is called to restore the heap property.

The heapifyUp(index) method compares the element at the given index with its parent and swaps them if necessary to restore the heap property. This process continues recursively until the heap property is satisfied.

By performing the heapify up operation after inserting a new element, we can ensure that the heap property is maintained and the new element is properly positioned within the heap.

xxxxxxxxxx

class MinHeap {

  private int[] heapArray;

  private int maxSize;

  private int heapSize;

​

  public MinHeap(int size) {

    maxSize = size;

    heapSize = 0;

    heapArray = new int[maxSize];

  }

​

  public void insert(int value) {

    if (isFull()) {

      System.out.println("Heap is full. Cannot insert.");

    } else {

      heapArray[heapSize] = value;

      heapSize++;

      heapifyUp(heapSize - 1);

    }

  }

​

  // Other methods...

}