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. The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for implementing heapsort.
A binary heap is defined as a binary tree with two additional constraints: 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 max-heaps; those where it is less than or equal to (≤) are called min-heaps. Efficient (that is, logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: Inserting an element; Removing the smallest or largest element from (respectively) a min-heap or max-heap. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm as 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 preserve 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 time.
Insert To insert an element to a heap, we perform the following steps:
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 up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, swim-up, heapify-up, cascade-up, or fix-up).
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 worst-case time complexity of . For a random heap, and for repeated insertions, the insertion operation has an average-case complexity of O(1).
The following animation depicts an example of binary heap insertion. It begins by inserting 15 into the heap at the left-most empty entry on the next available row. However, the heap property is violated since , so we need to swap the 15 and the 8. Even after this swap, the heap property is still violated since , so we need to swap again. The heap property is now satisfied, so the resulting binary tree is a valid max-heap. There is no need to check the left child after this final step: at the start, the max-heap 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 (; if , and , then , because of the transitive relation).
Extract The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) 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 min-heap and its larger child in a max-heap.) Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with one of its children, are called the down-heap (also known as bubble-down, percolate-down, sift-down, sink-down, trickle down, heapify-down, cascade-down, fix-down, extract-min or extract-max, or simply heapify) operation.
So, if we have the same max-heap 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 downward-moving node is swapped with the larger of its children in a max-heap (in a min-heap it would be swapped with its smaller child), until it satisfies the heap property in its new position. This functionality is achieved by the Max-Heapify function as defined below in pseudocode for an array-backed heap A of length length(A). A is indexed starting at 1.
// Perform a down-heap or heapify-down operation for a max-heap // A: an array representing the heap, indexed starting at 1 // i: the index to start at when heapifying down Max-Heapify(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] Max-Heapify(A, largest)
For the above algorithm to correctly re-heapify the array, no nodes besides the node at index i and its two direct children can violate the heap property. The down-heap 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 Down-heapify 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. 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. Push-Pop(heap: List<T>, item: T) -> T: if heap is not empty and heap > item then: // < if min heap swap heap 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 and item _downheap(heap starting from index 1) return item
Search Finding an arbitrary element takes O(n) time.
This can be easily proved by considering that the heap is not sorted so we need to look through the whole tree to find the target element.
Delete Deleting an arbitrary element can be done as follows:
Find the index of the element we want to delete Swap this element with the last element. Remove the last element after the swap. Down-heapify or up-heapify to restore the heap property. In a max-heap (min-heap), up-heapify is only required when the new key of element is greater (smaller) than the previous one because only the heap-property of the parent element might be violated. Assuming that the heap-property was valid between element 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 down-heapify is required because the heap-property 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 down-heapifying or up-heapifying 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 Down-heapify (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 Up-heapify (assuming a max heap) to restore the heap property
Building a heap (Heapify) Building a heap from an array of input elements can be done by starting with an empty heap, then successively inserting each element. Equivalently, the heap may be constructed by first arbitrarily placing the elements into the binary tree, then up-heapifying each node successively, which allows in-place heapification. This approach, called Williams' method after the inventor of binary heaps, is easily seen to run in time: it performs insertions at cost each.
However, Williams' method is suboptimal. A faster method (due to Floyd) 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 have already been "heapified" (the bottommost level corresponding to ), the trees at height can be heapified by sending their root down along the path of maximum valued children when building a max-heap, or minimum valued children when building a min-heap. This process takes operations (swaps) per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is , the number of nodes at height is . Therefore, the cost of heapifying all subtrees is:
This uses the fact that the given infinite series converges.
The exact value of the above (the worst-case number of comparisons during the heap construction) is known to be equal to:
,. where is the sum of all digits of the binary representation of and is the exponent of in the prime factorization of .
The average case is more complex to analyze, but it can be shown to asymptotically approach comparisons. Note that this paper uses Floyd's original terminology "siftup" for what is now called sifting down.
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify (down-heapify for a max-heap) in a bottom-up manner. The array elements indexed by , , ..., n are all leaves for the tree (assuming that indices start at 1)—thus each is a one-element heap, and does not need to be down-heapified. Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Build-Max-Heap (A): for each index i from floor(length(A)/2) downto 1 do: Max-Heapify(A, i)
Heap implementation