3

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.

Community
  • 1
  • 1
Yiliang
  • 463
  • 2
  • 6
  • 16
  • The Wikipedia article explains it quite well: http://en.wikipedia.org/wiki/Binomial_heap#Decrease_key – Jim Mischel Nov 13 '13 at 14:20
  • `decrease-key` takes O(log n). *Finding* the node, however, takes O(n) unless you maintain a reference to it in some other data structure. – Jim Mischel Nov 13 '13 at 15:34
  • 1
    Thanks Jim, I think we can probably maintain a hashtable structure, where each (key,value) pair stores the key and the pointer to the corresponding node. – Yiliang Nov 13 '13 at 23:15

1 Answers1

-1

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.

sunmoon
  • 1,448
  • 1
  • 15
  • 27
  • 1
    You're describing a [binary heap](http://en.wikipedia.org/wiki/Binary_heap), which is a much different thing than a [binomial heap](http://en.wikipedia.org/wiki/Binomial_heap). – Jim Mischel Nov 13 '13 at 14:21