The interface provided by the book "Introduction to Algorithm" of decreasing key in binomial heap is: BINOMIAL-HEAP-DECREASE-KEY (H,x,k), where H is the pointer to the first root of the tree, x is the "index" of the node, whose key is to be decreased to k. And the time complexity is O(logn)
However, we usually use linked list to implement the binomial heap, where there is no direct access to x without performing a search, which in general is O(n).
One way to solve this problem is to keep a pointer for each node in the binomial heap, which then make the direct access to every node in O(1) but the space complexity is then O(n).
Does anybody know better solutions for this? Thanks!
A previous discussion can be found here.
If we store the heap in an array we can easily do that.
If root element is at index i, left child is at 2i and right child is at 2i+1.
In an array we store the elements from index 1.
If we store the heap elements like this, we can directly decrement the element at index x and heapify from x.
This way for heapify we take o(logn) time. For decrementing it is constant.