Nick Smallbone wrote: > Well, a binomial (min-)heap is a tree where the value of the parent > node is less than the value of each child node. So the smallest must be > the one at the root of the tree.
You got confused between Binomial heap and Binary Heap. A binomial heap is a collection of Binomial trees. A binary (min)heap is a binary tree where each element is greater than its parent element. Check out the article on Wikipedia http://en.wikipedia.org/wiki/Binomial_heap As to the original posters question, we have to find the min of root nodes of binomial trees forming a binomial heap. If there are N trees, there will be N root nodes. We can arrange these N root nodes of binomial heap in a binary heap ( note: binary not binomial). Then getting MIN of root node operation is O(1). Just get the root node of binary heap which is formed of root nodes of trees from binomial heap. Alternatively, since root nodes of trees forming Binomail heap are arranged in a linked list, you can sort this linked list while constructing Binomial heap and get the first element when you want MIN. But both of these methods have overhead of preprocessing root nodes when construction Binomial heap. I don't think it is possible in pure Binomial heap to get MIN in O(1). The best you can do is O(N), where N is the number of root nodes. Tejas Kokje --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
