To implement a heap using an array, we need to decide how to manage that storage. One choice would be to use a fixed-size array. However, that would limit the number of elements the heap could store. To allow an arbitrary number of elements, we could instead choose to use a dynamic array (much like we do in an array based list). We would start with a small array and then resize it as needed when more space is required. In addition to the array itself, we would need to keep track of the current number of elements in the heap (the logical size) separately from the size of the array (the physical size).
template <typename T>
class Heap {
private:
T* m_data; // Dynamic array to store heap elements
size_t m_size; // Current number of elements in the heap
size_t m_capacity; // Current capacity of the array
};
Of course, in such a structure we would need to implement:
But all of that work is identical to what we would do for a dynamic array based list. So, we could instead choose to just use an array based list as the underlying storage for our heap. This would allow us to reuse all of that code and focus just on the heap specific logic.
template <typename T>
class Heap {
private:
vector<T> m_data; // Dynamic array (vector) to store heap elements
};
With this implementation, we do not have to worry about resizing the array or managing memory directly. The vector class takes care of that for us. We can simply use its methods to add and remove elements as needed. If we ask the vector for its size, it will give us the current number of elements in the heap.
In a heap, as in a dynamic array, we know the first “open” location is at the index equal to the current size of the heap. If the heap has 6 elements, they will be stored at indices 0 through 5, and the next open location will be at index 6. So that is the easiest place to insert a new element.
However, we can’t simply leave the new element there. We need to make sure that the heap property is maintained. If it has a value larger than its parent, the heap property is violated. To fix the issue, we can swap the element with its parent.
The parent might already have a child, but that other child (the sibling of the current element) must be less than the parent. So if we are replacing the parent with a larger value, any sibling to the current element that exists will still be less than the new parent value.
Of course, after swapping with the parent, we may have a new violation of the heap property with the parent’s parent. So we need to continue swapping up the tree until the heap property is restored or we reach the root.
The animation is ready to insert 15. Use the > button to step through the insertion process. Watch how the new value is added at the end of the array and then swapped up the tree to restore the heap property.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
function insert(value):
index = size()
add the new value at index (push back in the vector)
while index > 0:
parentIndex = floor((index - 1) / 2)
if data[index] > data[parentIndex]:
swap(data[index], data[parentIndex])
index = parentIndex
else:
break
All the work in this algorithm is constant (checking and swapping array elements can be done in constant time) with the exception of the loop. The loop could potentially run a number of times proportional to the height of the heap. Since the height of a complete binary tree is \(O(\log n)\text{,}\) where \(n\) is the number of elements in the heap, the overall time complexity of the loop, and thus the insert operation is \(O(\log n)\text{.}\)
