Binomial heap

"Binomial tree" redirects here. For binomial price trees, see binomial options pricing model.
Binomial heap
Typeheap
Invented1978
Invented byJean Vuillemin
Complexities in big O notation
Space complexity
Time complexity
Function Amortized Worst Case
Insert Θ(1) O(log n)
Find-min Θ(1) O(1)
Delete-min Θ(log n) O(log n)
Decrease-key Θ(log n) O(log n)
Merge Θ(log n) O(log n)

In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps.[1] Binomial heaps were invented in 1978 by Jean Vuillemin.[1][2]

  1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 19: Binomial Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. ISBN 0-262-03293-7.
  2. ^ Vuillemin, Jean (1 April 1978). "A data structure for manipulating priority queues". Communications of the ACM. 21 (4): 309–315. doi:10.1145/359460.359478.