Inserting an element into a heap
In this article we examine the idea laying in the foundation of the heap data structure. We call it sifting, but you also may meet another terms, like "trickle", "heapify", "bubble" or "percolate".
Insertion algorithm
Now, let us phrase general algorithm to insert a new element into a heap.
- Add a new element to the end of an array;
- Sift up the new element, while heap property is broken. Sifting is done as following: compare node's value with parent's value. If they are in wrong order, swap them.
Example
Insert -2 into a following heap:
Insert a new element to the end of the array:
In the general case, after insertion, heap property near the new node is broken:
Now heap property is broken at the root node:
Heap property is fulfilled, sifting is over.
Source heap |
After -2 insertion |
|
 |
Complexity analysis
Complexity of the insertion operation is O(h), where h is heap's height. Taking into account completeness of the tree, O(h) = O(log n), where n is number of elements in a heap.
Code snippets
Java implementation
public class BinaryMinHeap {
…
public void insert(int value) {
if (heapSize == data.length)
throw new HeapException("Heap's underlying storage is overflow");
else {
heapSize++;
data[heapSize - 1] = value;
siftUp(heapSize - 1);
}
}
…
private void siftUp(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;
siftUp(parentIndex);
}
}
}
}
C++ implementation
void BinaryMinHeap::siftUp(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;
siftUp(parentIndex);
}
}
}
void BinaryMinHeap::insert(int value) {
if (heapSize == arraySize)
throw string("Heap's underlying storage is overflow");
else {
heapSize++;
data[heapSize - 1] = value;
siftUp(heapSize - 1);
}
}
