Binary heap
Binary (min) heap  

Type  binary tree/heap  
Invented  1964  
Invented by  J. W. J. Williams  
Time complexity in big O notation  

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.^{[1]}^{:162–163} The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.^{[2]}
A binary heap is defined as a binary tree with two additional constraints:^{[3]}
 Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
 Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.
Heaps where the parent key is greater than or equal to (≥) the child keys are called maxheaps; those where it is less than or equal to (≤) are called minheaps. Efficient (logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: inserting an element, and removing the smallest or largest element from a minheap or maxheap, respectively. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an inplace algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child–parent relationships.
Heap operations
Both the insert and remove operations modify the heap to conform to the shape property first, by adding or removing from the end of the heap. Then the heap property is restored by traversing up or down the heap. Both operations take O(log n) time.
Insert
To add an element to a heap, we can perform this algorithm:
 Add the element to the bottom level of the heap at the leftmost open space.
 Compare the added element with its parent; if they are in the correct order, stop.
 If not, swap the element with its parent and return to the previous step.
Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with its parent, are called the upheap operation (also known as bubbleup, percolateup, siftup, trickleup, swimup, heapifyup, or cascadeup).
The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property. Thus, the insertion operation has a worstcase time complexity of O(log n). For a random heap, and for repeated insertions, the insertion operation has an averagecase complexity of O(1).^{[4]}^{[5]}
As an example of binary heap insertion, say we have a maxheap
and we want to add the number 15 to the heap. We first place the 15 in the position marked by the X. However, the heap property is violated since 15 > 8, so we need to swap the 15 and the 8. So, we have the heap looking as follows after the first swap:
However the heap property is still violated since 15 > 11, so we need to swap again:
which is a valid maxheap. There is no need to check the left child after this final step: at the start, the maxheap was valid, meaning the root was already greater than its left child, so replacing the root with an even greater value will maintain the property that each node is greater than its children (11 > 5; if 15 > 11, and 11 > 5, then 15 > 5, because of the transitive relation).
Extract
The procedure for deleting the root from the heap (effectively extracting the maximum element in a maxheap or the minimum element in a minheap) while retaining the heap property is as follows:
 Replace the root of the heap with the last element on the last level.
 Compare the new root with its children; if they are in the correct order, stop.
 If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a minheap and its larger child in a maxheap.)
Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with one of its children, are called the downheap (also known as bubbledown, percolatedown, siftdown, sinkdown, trickle down, heapifydown, cascadedown, extractmin or extractmax, or simply heapify) operation.
So, if we have the same maxheap as before
We remove the 11 and replace it with the 4.
Now the heap property is violated since 8 is greater than 4. In this case, swapping the two elements, 4 and 8, is enough to restore the heap property and we need not swap elements further:
The downwardmoving node is swapped with the larger of its children in a maxheap (in a minheap it would be swapped with its smaller child), until it satisfies the heap property in its new position. This functionality is achieved by the MaxHeapify function as defined below in pseudocode for an arraybacked heap A of length length(A). A is indexed starting at 1.
// Perform a downheap or heapifydown operation for a maxheap // A: an array representing the heap, indexed starting at 1 // i: the index to start at when heapifying down MaxHeapify(A, i): left ← 2×i right ← 2×i + 1 largest ← i if left ≤ length(A) and A[left] > A[largest] then: largest ← left
if right ≤ length(A) and A[right] > A[largest] then: largest ← right if largest ≠ i then: swap A[i] and A[largest] MaxHeapify(A, largest)
For the above algorithm to correctly reheapify the array, no nodes besides the node at index i and its two direct children can violate the heap property. The downheap operation (without the preceding swap) can also be used to modify the value of the root, even when an element is not being deleted.
In the worst case, the new root has to be swapped with its child on each level until it reaches the bottom level of the heap, meaning that the delete operation has a time complexity relative to the height of the tree, or O(log n).
Insert then extract
Inserting an element then extracting from the heap can be done more efficiently than simply calling the insert and extract functions defined above, which would involve both an upheap and downheap operation. Instead, we can do just a downheap operation, as follows:
 Compare whether the item we're pushing or the peeked top of the heap is greater (assuming a max heap)
 If the root of the heap is greater:
 Replace the root with the new item
 Downheapify starting from the root
 Else, return the item we're pushing
Python provides such a function for insertion then extraction called "heappushpop", which is paraphrased below.^{[6]}^{[7]} The heap array is assumed to have its first element at index 1.
// Push a new item to a (max) heap and then extract the root of the resulting heap. // heap: an array representing the heap, indexed at 1 // item: an element to insert // Returns the greater of the two between item and the root of heap. PushPop(heap: List<T>, item: T) > T: if heap is not empty and heap[1] > item then: // < if min heap swap heap[1] and item _downheap(heap starting from index 1) return item
A similar function can be defined for popping and then inserting, which in Python is called "heapreplace":
// Extract the root of the heap, and push a new item // heap: an array representing the heap, indexed at 1 // item: an element to insert // Returns the current root of heap Replace(heap: List<T>, item: T) > T: swap heap[1] and item _downheap(heap starting from index 1) return item
Search
Finding an arbitrary element takes O(n) time.
Delete
Deleting an arbitrary element can be done as follows:
 Find the index [math]\displaystyle{ i }[/math] of the element we want to delete
 Swap this element with the last element
 Downheapify or upheapify to restore the heap property. In a maxheap (minheap), upheapify is only required when the new key of element [math]\displaystyle{ i }[/math] is greater (smaller) than the previous one because only the heapproperty of the parent element might be violated. Assuming that the heapproperty was valid between element [math]\displaystyle{ i }[/math] and its children before the element swap, it can't be violated by a now larger (smaller) key value. When the new key is less (greater) than the previous one then only a downheapify is required because the heapproperty might only be violated in the child elements.
Decrease or increase key
The decrease key operation replaces the value of a node with a given value with a lower value, and the increase key operation does the same but with a higher value. This involves finding the node with the given value, changing the value, and then downheapifying or upheapifying to restore the heap property.
Decrease key can be done as follows:
 Find the index of the element we want to modify
 Decrease the value of the node
 Downheapify (assuming a max heap) to restore the heap property
Increase key can be done as follows:
 Find the index of the element we want to modify
 Increase the value of the node
 Upheapify (assuming a max heap) to restore the heap property
Building a heap
Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element. This approach, called Williams' method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.^{[loweralpha 1]}
However, Williams' method is suboptimal. A faster method (due to Floyd^{[8]}) starts by arbitrarily putting the elements on a binary tree, respecting the shape property (the tree could be represented by an array, see below). Then starting from the lowest level and moving upwards, sift the root of each subtree downward as in the deletion algorithm until the heap property is restored. More specifically if all the subtrees starting at some height [math]\displaystyle{ h }[/math] have already been "heapified" (the bottommost level corresponding to [math]\displaystyle{ h=0 }[/math]), the trees at height [math]\displaystyle{ h+1 }[/math] can be heapified by sending their root down along the path of maximum valued children when building a maxheap, or minimum valued children when building a minheap. This process takes [math]\displaystyle{ O(h) }[/math] operations (swaps) per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is [math]\displaystyle{ \lfloor \log n \rfloor }[/math], the number of nodes at height [math]\displaystyle{ h }[/math] is [math]\displaystyle{ \le \frac{2^{\lfloor \log n \rfloor}}{2^h} \le \frac{n}{2^h} }[/math]. Therefore, the cost of heapifying all subtrees is:
 [math]\displaystyle{ \begin{align} \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^h} O(h) & = O\left(n\sum_{h=0}^{\lfloor \log n \rfloor} \frac{h}{2^h}\right) \\ & = O\left(n\sum_{h=0}^{\infty} \frac{h}{2^h}\right) \\ & = O(n) \end{align} }[/math]
This uses the fact that the given infinite series [math]\displaystyle{ \sum_{i=0}^\infty i/2^i }[/math] converges.
The exact value of the above (the worstcase number of comparisons during the heap construction) is known to be equal to:
 [math]\displaystyle{ 2 n  2 s_2 (n)  e_2 (n) }[/math],^{[9]}^{[loweralpha 2]}
where s_{2}(n) is the sum of all digits of the binary representation of n and e_{2}(n) is the exponent of 2 in the prime factorization of n.
The average case is more complex to analyze, but it can be shown to asymptotically approach 1.8814 n − 2 log_{2}n + O(1) comparisons.^{[10]}^{[11]}
The BuildMaxHeap function that follows, converts an array A which stores a complete binary tree with n nodes to a maxheap by repeatedly using MaxHeapify (downheapify for a maxheap) in a bottomup manner. The array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1)—thus each is a oneelement heap, and does not need to be downheapified. BuildMaxHeap runs MaxHeapify on each of the remaining tree nodes.
BuildMaxHeap (A): for each index i from floor(length(A)/2) downto 1 do: MaxHeapify(A, i)
Heap implementation
Heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices. These properties make this heap implementation a simple example of an implicit data structure or Ahnentafel list. Details depend on the root position, which in turn may depend on constraints of a programming language used for implementation, or programmer preference. Specifically, sometimes the root is placed at index 1, in order to simplify arithmetic.
Let n be the number of elements in the heap and i be an arbitrary valid index of the array storing the heap. If the tree root is at index 0, with valid indices 0 through n − 1, then each element a at index i has
 children at indices 2i + 1 and 2i + 2
 its parent at index floor((i − 1) / 2).
Alternatively, if the tree root is at index 1, with valid indices 1 through n, then each element a at index i has
 children at indices 2i and 2i +1
 its parent at index floor(i / 2).
This implementation is used in the heapsort algorithm which reuses the space allocated to the input array to store the heap (i.e. the algorithm is done inplace). This implementation is also useful as a Priority queue. When a dynamic array is used, insertion of an unbounded number of items is possible.
The upheap/downheap operations can then be stated in terms of an array as follows: suppose that the heap property holds for the indices b, b+1, ..., e. The siftdown function extends the heap property to b−1, b, b+1, ..., e. Only index i = b−1 can violate the heap property. Let j be the index of the largest child of a[i] (for a maxheap, or the smallest child for a minheap) within the range b, ..., e. (If no such index exists because 2i > e then the heap property holds for the newly extended range and nothing needs to be done.) By swapping the values a[i] and a[j] the heap property for position i is established. At this point, the only problem is that the heap property might not hold for index j. The siftdown function is applied tailrecursively to index j until the heap property is established for all elements.
The siftdown function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log_{2} e steps are required.
For big heaps and using virtual memory, storing elements in an array according to the above scheme is inefficient: (almost) every level is in a different page. Bheaps are binary heaps that keep subtrees in a single page, reducing the number of pages accessed by up to a factor of ten.^{[12]}
The operation of merging two binary heaps takes Θ(n) for equalsized heaps. The best you can do is (in case of array implementation) simply concatenating the two heap arrays and build a heap of the result.^{[13]} A heap on n elements can be merged with a heap on k elements using O(log n log k) key comparisons, or, in case of a pointerbased implementation, in O(log n log k) time.^{[14]} An algorithm for splitting a heap on n elements into two heaps on k and nk elements, respectively, based on a new view of heaps as an ordered collections of subheaps was presented in.^{[15]} The algorithm requires O(log n * log n) comparisons. The view also presents a new and conceptually simple algorithm for merging heaps. When merging is a common task, a different heap implementation is recommended, such as binomial heaps, which can be merged in O(log n).
Additionally, a binary heap can be implemented with a traditional binary tree data structure, but there is an issue with finding the adjacent element on the last level on the binary heap when adding an element. This element can be determined algorithmically or by adding extra data to the nodes, called "threading" the tree—instead of merely storing references to the children, we store the inorder successor of the node as well.
It is possible to modify the heap structure to make the extraction of both the smallest and largest element possible in [math]\displaystyle{ O }[/math][math]\displaystyle{ (\log n) }[/math] time.^{[16]} To do this, the rows alternate between min heap and maxheap. The algorithms are roughly the same, but, in each step, one must consider the alternating rows with alternating comparisons. The performance is roughly the same as a normal single direction heap. This idea can be generalized to a minmaxmedian heap.
Derivation of index equations
In an arraybased heap, the children and parent of a node can be located via simple arithmetic on the node's index. This section derives the relevant equations for heaps with their root at index 0, with additional notes on heaps with their root at index 1.
To avoid confusion, we'll define the level of a node as its distance from the root, such that the root itself occupies level 0.
Child nodes
For a general node located at index i (beginning from 0), we will first derive the index of its right child, [math]\displaystyle{ \text{right} = 2i + 2 }[/math].
Let node i be located in level L, and note that any level l contains exactly [math]\displaystyle{ 2^l }[/math] nodes. Furthermore, there are exactly [math]\displaystyle{ 2^{l + 1}  1 }[/math] nodes contained in the layers up to and including layer l (think of binary arithmetic; 0111...111 = 1000...000  1). Because the root is stored at 0, the kth node will be stored at index [math]\displaystyle{ (k  1) }[/math]. Putting these observations together yields the following expression for the index of the last node in layer l.
 [math]\displaystyle{ \text{last}(l) = (2^{l + 1}  1)  1 = 2^{l + 1}  2 }[/math]
Let there be j nodes after node i in layer L, such that
 [math]\displaystyle{ \begin{alignat}{2} i = & \quad \text{last}(L)  j\\ = & \quad (2^{L + 1} 2)  j\\ \end{alignat} }[/math]
Each of these j nodes must have exactly 2 children, so there must be [math]\displaystyle{ 2j }[/math] nodes separating i's right child from the end of its layer ([math]\displaystyle{ L + 1 }[/math]).
 [math]\displaystyle{ \begin{alignat}{2} \text{right} = & \quad \text{last(L + 1)} 2j\\ = & \quad (2^{L + 2} 2) 2j\\ = & \quad 2(2^{L + 1} 2 j) + 2\\ = & \quad 2i + 2 \end{alignat} }[/math]
As required.
Noting that the left child of any node is always 1 place before its right child, we get [math]\displaystyle{ \text{left} = 2i + 1 }[/math].
If the root is located at index 1 instead of 0, the last node in each level is instead at index [math]\displaystyle{ 2^{l + 1}  1 }[/math]. Using this throughout yields [math]\displaystyle{ \text{left} = 2i }[/math] and [math]\displaystyle{ \text{right} = 2i + 1 }[/math] for heaps with their root at 1.
Parent node
Every node is either the left or right child of its parent, so we know that either of the following is true.
 [math]\displaystyle{ i = 2 \times (\text{parent}) + 1 }[/math]
 [math]\displaystyle{ i = 2 \times (\text{parent}) + 2 }[/math]
Hence,
 [math]\displaystyle{ \text{parent} = \frac{i  1}{2} \;\textrm{ or }\; \frac{i  2}{2} }[/math]
Now consider the expression [math]\displaystyle{ \left\lfloor \dfrac{i  1}{2} \right\rfloor }[/math].
If node [math]\displaystyle{ i }[/math] is a left child, this gives the result immediately, however, it also gives the correct result if node [math]\displaystyle{ i }[/math] is a right child. In this case, [math]\displaystyle{ (i  2) }[/math] must be even, and hence [math]\displaystyle{ (i  1) }[/math] must be odd.
 [math]\displaystyle{ \begin{alignat}{2} \left\lfloor \dfrac{i  1}{2} \right\rfloor = & \quad \left\lfloor \dfrac{i  2}{2} + \dfrac{1}{2} \right\rfloor\\ = & \quad \frac{i  2}{2}\\ = & \quad \text{parent} \end{alignat} }[/math]
Therefore, irrespective of whether a node is a left or right child, its parent can be found by the expression:
 [math]\displaystyle{ \text{parent} = \left\lfloor \dfrac{i  1}{2} \right\rfloor }[/math]
Related structures
Since the ordering of siblings in a heap is not specified by the heap property, a single node's two children can be freely interchanged unless doing so violates the shape property (compare with treap). Note, however, that in the common arraybased heap, simply swapping the children might also necessitate moving the children's subtree nodes to retain the heap property.
The binary heap is a special case of the dary heap in which d = 2.
Summary of running times
Here are time complexities^{[17]} of various heap data structures. Function names assume a minheap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation  findmin  deletemin  insert  decreasekey  meld 

Binary^{[17]}  Θ(1)  Θ(log n)  O(log n)  O(log n)  Θ(n) 
Leftist  Θ(1)  Θ(log n)  Θ(log n)  O(log n)  Θ(log n) 
Binomial^{[17]}^{[18]}  Θ(1)  Θ(log n)  Θ(1)^{[loweralpha 3]}  Θ(log n)  O(log n)^{[loweralpha 4]} 
Fibonacci^{[17]}^{[19]}  Θ(1)  O(log n)^{[loweralpha 3]}  Θ(1)  Θ(1)^{[loweralpha 3]}  Θ(1) 
Pairing^{[20]}  Θ(1)  O(log n)^{[loweralpha 3]}  Θ(1)  o(log n)^{[loweralpha 3]}^{[loweralpha 5]}  Θ(1) 
Brodal^{[23]}^{[loweralpha 6]}  Θ(1)  O(log n)  Θ(1)  Θ(1)  Θ(1) 
Rankpairing^{[25]}  Θ(1)  O(log n)^{[loweralpha 3]}  Θ(1)  Θ(1)^{[loweralpha 3]}  Θ(1) 
Strict Fibonacci^{[26]}  Θ(1)  O(log n)  Θ(1)  Θ(1)  Θ(1) 
23 heap^{[27]}  O(log n)  O(log n)^{[loweralpha 3]}  O(log n)^{[loweralpha 3]}  Θ(1)  ? 
 ↑ In fact, this procedure can be shown to take Θ(n log n) time in the worst case, meaning that n log n is also an asymptotic lower bound on the complexity.^{[1]}^{:167} In the average case (averaging over all permutations of n inputs), though, the method takes linear time.^{[8]}
 ↑ This does not mean that sorting can be done in linear time since building a heap is only the first step of the heapsort algorithm.
 ↑ ^{3.0} ^{3.1} ^{3.2} ^{3.3} ^{3.4} ^{3.5} ^{3.6} ^{3.7} ^{3.8} Amortized time.
 ↑ n is the size of the larger heap.
 ↑ Lower bound of [math]\displaystyle{ \Omega(\log\log n), }[/math]^{[21]} upper bound of [math]\displaystyle{ O(2^{2\sqrt{\log\log n}}). }[/math]^{[22]}
 ↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decreasekey, which is not supported. Heaps with n elements can be constructed bottomup in O(n).^{[24]}
See also
References
 ↑ ^{1.0} ^{1.1} Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGrawHill. ISBN 0262033844.
 ↑ Williams, J. W. J. (1964), "Algorithm 232  Heapsort", Communications of the ACM 7 (6): 347–348, doi:10.1145/512274.512284
 ↑ eEL,CSA_Dept,IISc,Bangalore, "Binary Heaps", Data Structures and Algorithms, http://lcm.csa.iisc.ernet.in/dsa/node137.html
 ↑ Porter, Thomas; Simon, Istvan (Sep 1975). "Random insertion into a priority queue structure". IEEE Transactions on Software Engineering SE1 (3): 292–298. doi:10.1109/TSE.1975.6312854. ISSN 19393520.
 ↑ Mehlhorn, Kurt; Tsakalidis, A. (Feb 1989) (in en). Data structures. Universität des Saarlandes. pp. 27. doi:10.22028/D29126123. https://publikationen.sulb.unisaarland.de/handle/20.500.11880/26179. "Porter and Simon [171] analyzed the average cost of inserting a random element into a random heap in terms of exchanges. They proved that this average is bounded by the constant 1.61. Their proof docs not generalize to sequences of insertions since random insertions into random heaps do not create random heaps. The repeated insertion problem was solved by Bollobas and Simon [27]; they show that the expected number of exchanges is bounded by 1.7645. The worstcase cost of inserts and deletemins was studied by Gonnet and Munro [84]; they give log log n + O(1) and log n + log n* + O(1) bounds for the number of comparisons respectively.".
 ↑ "python/cpython/heapq.py" (in en). https://github.com/python/cpython/blob/master/Lib/heapq.py.
 ↑ "heapq — Heap queue algorithm — Python 3.8.5 documentation". https://docs.python.org/3/library/heapq.html#heapq.heappushpop. "heapq.heappushpop(heap, item): Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop()."
 ↑ ^{8.0} ^{8.1} Hayward, Ryan; McDiarmid, Colin (1991). "Average Case Analysis of Heap Building by Repeated Insertion". J. Algorithms 12: 126–153. doi:10.1016/01966774(91)90027v. http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf. Retrieved 20160128.
 ↑ Suchenek, Marek A. (2012), "Elementary Yet Precise WorstCase Analysis of Floyd's HeapConstruction Program", Fundamenta Informaticae 120 (1): 75–92, doi:10.3233/FI2012751, http://www.deepdyve.com/lp/iospress/elementaryyetpreciseworstcaseanalysisoffloydsheap50NW30HMxU.
 ↑ Doberkat, Ernst E. (May 1984). "An Average Case Analysis of Floyd's Algorithm to Construct Heaps". Information and Control 6 (2): 114–131. doi:10.1016/S00199958(84)800534. https://core.ac.uk/download/pdf/82135122.pdf.
 ↑ Pasanen, Tomi (November 1996). Elementary Average Case Analysis of Floyd's Algorithm to Construct Heaps (Technical report). Turku Centre for Computer Science. CiteSeerX 10.1.1.15.9526. ISBN 951650888X. TUCS Technical Report No. 64. Note that this paper uses Floyd's original terminology "siftup" for what is now called sifting down.
 ↑ Kamp, PoulHenning (June 11, 2010). "You're Doing It Wrong". ACM Queue 8 (6). http://queue.acm.org/detail.cfm?id=1814327.
 ↑ Chris L. Kuszmaul. "binary heap" . Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009.
 ↑ J.R. Sack and T. Strothotte "An Algorithm for Merging Heaps", Acta Informatica 22, 171186 (1985).
 ↑ Sack, JörgRüdiger; Strothotte, Thomas (1990). "A characterization of heaps and its applications". Information and Computation 86: 69–86. doi:10.1016/08905401(90)90026E.
 ↑ Atkinson, M.D.; J.R. Sack (1 October 1986). "Minmax heaps and generalized priority queues.". Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf.
 ↑ ^{17.0} ^{17.1} ^{17.2} ^{17.3} Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGrawHill. ISBN 0262031418.
 ↑ "Binomial Heap  Brilliant Math & Science Wiki" (in enus). https://brilliant.org/wiki/binomialheap/.
 ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery 34 (3): 596615. doi:10.1145/28869.28874. http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/FibonacciHeapTarjan.pdf.
 ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, SpringerVerlag, pp. 63–77, doi:10.1007/354044985X_5, ISBN 3540676902, http://john2.poly.edu/papers/swat00/paper.pdf
 ↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures". Journal of the Association for Computing Machinery 46 (4): 473–501. doi:10.1145/320211.320214. http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf.
 ↑ Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps". FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. doi:10.1109/SFCS.2005.75. ISBN 0769524680. http://web.eecs.umich.edu/~pettie/papers/focs05.pdf.
 ↑ Brodal, Gerth S. (1996), "WorstCase Efficient Priority Queues", Proc. 7th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 52–58, http://www.cs.au.dk/~gerth/papers/soda96.pdf
 ↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. BottomUp Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338341. ISBN 0471469831.
 ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rankpairing heaps". SIAM J. Computing 40 (6): 1463–1485. doi:10.1137/100785351. http://sidsen.org/papers/rpheapsjournal.pdf.
 ↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). "Strict Fibonacci heaps". Proceedings of the 44th symposium on Theory of Computing  STOC '12. pp. 1177–1184. doi:10.1145/2213977.2214082. ISBN 9781450312455. http://www.cs.au.dk/~gerth/papers/stoc12.pdf.
 ↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps, pp. 12, https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/23heaps.pdf
External links
 Open Data Structures  Section 10.1  BinaryHeap: An Implicit Binary Tree, Pat Morin
 Implementation of binary max heap in C by Robin Thomas
 Implementation of binary min heap in C by Robin Thomas
Original source: https://en.wikipedia.org/wiki/Binary heap.
Read more 