The code below is part of a ____ data structure. public class Mystery { … public
ID: 3926258 • Letter: T
Question
The code below is part of a ____ data structure.
public class Mystery {
…
public void insert(int value) {
if (size == data.length)
throw new Exception("Underlying storage is overflow");
else {
size++;
data[size - 1] = value;
siftUp(size - 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);
}
}
}
}
Skip list
Tree (this is a recursive tree traversal algorithm)
Priority queue
Deque
Stack
Hash table
Map
Heap
Skip list
Tree (this is a recursive tree traversal algorithm)
Priority queue
Deque
Stack
Hash table
Map
Heap
Explanation / Answer
In this article we examine the idea laying in the foundation of the heap data structure. We call it sifting.
Insertion algorithm
Now, let us phrase general algorithm to insert a new element into a heap.
1. Add a new element to the end of an array;
2. 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:
To restore heap property, algorithm sifts up the new element, by swapping it with its parent:
Now heap property is broken at the root node:
Keep sifting:
Heap property is fulfilled, sifting is over.
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.