Search code examples
data-structurestime-complexitybig-obinomial-heap

Delete and Increase key for Binomial heap

I currently studying the binomial heap right now.

I learned that following operations for the binomial heaps can be completed in Theta(log n) time.:

  1. Get-max
  2. Insert
  3. Extract Max
  4. Merge
  5. Increase-Key
  6. Delete

But, the two operations Increase key and Delete operations said they need the pointer to the element that need to be complete in Theta(log n).

Here is 3 questions I want to ask:

  1. Is this because if Increase key and Delete don't have the pointer to element, they have to search the elements before the operations took place?

  2. what is the time complexity for the searching operations for the binomial heap? (I believe O(n))

  3. If the pointer to the element is not given for Increase key and Delete operations, those two operations will take O(n) time or it can be lower than that.

Solution

  • It’s good that you’re thinking about this!

    1. Yes, that’s exactly right. The nodes in a binomial heap are organized in a way that makes it very quick to find the minimum value, but the relative ordering of the remaining elements is not guaranteed to be in an order that makes it easy to find things.

    2. There isn’t a general way to search a binomial heap for an element faster than O(n). Or, stated differently, the worst-case cost of any way of searching a binomial heap is Ω(n). Here’s one way to see this. Form a binomial heap where n-1 items have priority 137 and one item has priority 42. The item with priority 42 must be a leaf node. There are (roughly) n/2 leaves in the heap, and since there is no ordering on them to find that one item you’d have to potentially look at all the leaves. To formalize this, you could form multiple different binomial heaps with these items, and whatever algorithm was looking for the item of priority 42 would necessarily have to find it in the last place it looks at least once.

    3. For the reasons given above, no, there’s no way to implement those operations quickly without having pointers to them, since in the worst case you have to search everywhere.