Fast queries and min heap →
In a previous post we came to know of this awesome data structure that could be used when we want to do fast retrieval of elements with maximum or minimum key values. In such cases, we do not need to sort the entire set of elements. In this post, we will see the implementation of Min Heap (which allows us to retrieve minimum element efficiently). Implementation of Max Heap follows a similar structure and is straight forward.
In this particular C++ implementation we use std::vector
as the container for the elements of the heap. We ignore index 0
and our elements are stored from index 1
. This is just to keep track of parent and children nodes easily. For any node k, the parent node would be at k/2 and children nodes at indices 2k and 2k + 1.
Further, we will start with the following signature that provides the client methods to insert a new key insert_item()
, retrieve the min valued key get_min()
and also delete the min valued key delete_min()
from the structure.
The constructor is straight-forward. We just create a vector of capacity one more than the specified one (as we are ignoring entry at index 0
).
Retrieving the min valued key is also straight-forward - just get the root of the tree. That is the beauty of this data structure. The way we accomplish having the min valued key always at the root is a little involved and it is incorporated into insert_item()
and delete_min()
methods.
We will see insert_item()
and delete_min()
methods in a future post.