Heap : Inserting an element into a heap using BubbleUp

Lets consider the min heap here.

Inserting the key k in the given heap. Consider the heap:

1. Insert k at the end of the last level

2. a) If the heap property is not broken you are done. Suppose k = 10. Here 10 is more than 4, hence min-heap property i.e. parent < child is already followed. Hence everything ok.
   
   
   
   b)If the heap property is broken, then you have to bubble up the added child until heap property is restored. Suppose k = 5.
   
   As, we can see the 5 and 12 have problem, we bubble up 5 by swapping it with 12:
   
   
   
   
   
   
   Now after swapping 5 and 12, we see still the heap property is not restored, hence we swap 8 with 5.
   
   
   
   
   
   After swapping 5 and 8, we see that heap property is restored.

Here is the implementation of heap insertion in java:

public void insert(int value) {

    if (heapSize == data.length)
          throw new HeapException("Heap's underlying storage is overflow");

    else {

          heapSize++;
          data[heapSize - 1] = value;
          bubbleUp(heapSize - 1);
    }
}
   
private void bubbleUp(int nodeIndex) {

    int parentIndex, tmp;

    if (nodeIndex != 0) {
          parentIndex = getParentIndex(nodeIndex);
          if (data[parentIndex] > data[nodeIndex]) {
                tmp = data[parentIndex];
                data[parentIndex] = data[nodeIndex];
                data[nodeIndex] = tmp;
                bubbleUp(parentIndex);
          }
    }

}