Lets consider the min heap here.
Inserting the key k in the given heap. Consider the heap:
- Insert k at the end of the last level
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);
}
}
}