A binomial heap is a type of priority queue data structure implemented as a forest of binomial trees. Binomial heaps support fast insertion, deletion, and merging.
Questions tagged [binomial-heap]
37 questions
22
votes
3 answers
What is the difference between binary heaps and binomial heaps?
I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children.
I am actually just…
Abdul Samad
- 5,748
- 17
- 56
- 70
12
votes
4 answers
binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue
Could someone please explain me how should I decide whether to use one or another heap implementation, among the ones mentioned in the title?
I would like an answer to guide me on choosing the implementation regarding the performance of the…
Throoze
- 3,988
- 8
- 45
- 67
9
votes
0 answers
Can skew binomial heaps support efficient merge?
The skew binomial heaps described in Okasaki's Purely Functional Data Structures support merge in worst-case O(log (max (m,n))) time, where m and n are the lengths of the queues being merged. This is worse than segmented binomial queues, which…
dfeuer
- 48,079
- 5
- 63
- 167
4
votes
0 answers
Should melding/merging of binomial heaps be done in one pass or two?
Okasaki's implementation in Purely Functional Data Structures (page 22) does it in two: one to merge the forest, and one to propagate the carries. This strikes me as harder to analyze, and also probably slower, than a one-pass version. Am I missing…
dfeuer
- 48,079
- 5
- 63
- 167
3
votes
2 answers
Why is the merge function of binomial heaps O(logN) rather than O(logN * logN)?
For those who know this very well, just read the bolded text below for the actual question.
Preface of auxilliary functions:
I know that merging two binomial trees of the same rank is O(1) since all that's necessary is to append the head of T1 as…
OneRaynyDay
- 3,658
- 2
- 23
- 56
3
votes
1 answer
Binomial Heap implementation in Python 2.7
I'm looking for a Python implementation of Binomial Heap and I noticed that the codes don't have decreaseKey implemented. Why in Binomial Heap nobody implements decreaseKey?
Roberto Pavia
- 75
- 7
3
votes
1 answer
How to make decrease-key in binomial heap run in logarithm time
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…
Yiliang
- 463
- 2
- 6
- 16
3
votes
2 answers
Correct functional implementation on Binomial Heap
I am reading Binomial Heap in Purely Functional Data Structures.
The implementation of insTree function confused me quite much. Here are the set of codes
datatype Tree = Node of int * Elem.T * Tree list
fun link (t1 as Node (r, x1, c1), t2 as Node…
Jackson Tale
- 25,428
- 34
- 149
- 271
2
votes
1 answer
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.:
Get-max
Insert
Extract Max
Merge
Increase-Key
Delete
But, the two operations Increase key and…
TONY
- 25
- 4
2
votes
2 answers
Binomial heap sibling - linked list reversal
I don't understand the reversal of the list of a node l in a binomial heap:
Node* reverseList(Node* l) {
//return reverseNode(l);
if(l->sibling)
{
return reverseList(l->sibling);
l->sibling->sibling = l;
}
}
What…
Ștefan Tătărucă
- 47
- 5
2
votes
1 answer
Why can't we sort N numbers in comparison sorting algorithm faster than O(n log n) time?
I was looking into binary, binomial and Fibonacci heap sort and I found out that takes O(n log n) time to sort. It would be great if someone can give me a reason as to why it is so.
Somit
- 51
- 3
2
votes
2 answers
When would it be preferred to implement a priority queue with a Singly Linked List over a Heap?
I recently just started up a project with some code that has been already written. I decided to look into his implementation and found that he implemented a Priority Queue with a Singly Linked List.
My understanding of SLLs is that since you may…
HD_Mouse
- 567
- 1
- 7
- 19
2
votes
0 answers
Printing the contents of a binomial heap in ascending/descending order
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…
Wugafuzza
- 31
- 2
2
votes
1 answer
How insert operation has an amortized time of O(1) in binomial heap?
Wikipedia says that the insert operation in binomial heap has an amortized time of O(1). For a single insert operation the time complexity is O(log n). But how its amortised time becomes O(1)?
Hari Krishnan
- 5,992
- 9
- 37
- 55
2
votes
1 answer
Prove the number of binomial trees in a binomial heap with n elements is at most O(log n)
I am having trouble locating a good proof for this statement. I know how to determine the number of binomial trees is determined by using the binary representation of n.
For example, 13 elements is 1101 in binary, 2^{3}+2^{2}+2^{0} So 3 binomial…
Brian
- 7,098
- 15
- 56
- 73