2

Given that a binomial heap is a collection of binomial trees, I am having difficulty understanding how we can efficiently print out the contents of a binomial heap in ascending/descending order (depending on if it is a min/max heap).

Currently the method I am using is creating a clone of the heap and extracting the minimum (as this is a minimum binomial heap) until all the elements have been extracted. This would result in O(n*log(n)) time if I understand it correctly, which is quite a long process.

Is there any way of speeding up this process, or some other alternative method of printing out the contents of a binomial heap in ascending order?

Wugafuzza
  • 31
  • 2
  • 1
    Why do you say ithat heapsort is slow? O(n log n) is the mathematical limit for comparison sorting. – Kenny Ostrom May 18 '18 at 13:04
  • Well the reason I chose to use a binomial heap was for the fast times in all the other areas such as merging, insertion and deletion. Given that the the printing of the heap would take O(nlog(n)) time and this process will be done many times, it makes the entire structure less efficient dealing with the data. – Wugafuzza May 18 '18 at 18:42
  • 1
    I was saying that's not slow ... but for something you repeat many times, it is slow because you forget the work each time. Gotcha. So two great data structures for different operations, but you need both at the same time. Can you maintain both in parallel, or just cache the sorted output? – Kenny Ostrom May 19 '18 at 16:24
  • The problem with keeping both structures would be if I change add data for example into the Binomial Heap, or merge it with another Binomial Heap that is not sorted, then to print the the heap would have to sort the whole data set once again. Of course, I might be overlooking something, in which I would be very thankful if you can see some error in my logic. – Wugafuzza May 19 '18 at 18:41
  • If you maintain a sorted list in a separate but related datastructure, and you add one thing, you could a) regenerate the entire sorted list from the binomial heap in an expensive operation, or b) add it to the heap normally, and independently add it to the sorted list with a binary search (log n), because it's a completely independent data structure you are maintaining in parallel. The downside is bookeeping hassle to keep both synchronized on ALL operations. The upside is you can do it efficiently using separate methods for each. (or just flag the sorted list dirty for some ops) – Kenny Ostrom May 26 '18 at 14:22

0 Answers0