Question

Consider a binomial heap where only insert and findmin operations are allowed (no extractmin). Show that both of these operations can be done in amortized O(1) time. Hint: For findmin consider explicitely storing a pointer to the tree with minimum root and then update it during insert if needed. For insert, you’ll need to use amortization and develop a good potential function.

Answer 1

Solution: A binomial heap is actually nothing but a collection of min heaps. Since we know that in a min-heap, the minimum element is always present at the root node of the tree, therefore, the minimum element can always be found at the top of the tree in a constant amount of time that is O(1). It can be easily performed by traversing to the minimum root node of the tree which can be implemented using a pointer that is always pointing to the minimum key root of the binomial tree.

On, the other hand, the insertion in the tree has to be done at the leaves and hence the heapify algorithm has to be called within that heap of the binomial heap and hence it would take O(log N) of time where n is nothing but the level of the particular heap within the binomial heap and hence the insertion would take O(1) of time but the heapify would be called and it would take an additional O(log N) time.

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!