Binary heap
[1]: 162–163 The binary heap was introduced by J. W. J. Williams in 1964 as a data structure for implementing heapsort.
[2] A binary heap is defined as a binary tree with two additional constraints:[3] 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: Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place 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.
To insert an element to a heap, we perform the following steps: 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).
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 (11 > 5; if 15 > 11, and 11 > 5, then 15 > 5, because of the transitive relation).
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: 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.
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).
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: Python provides such a function for insertion then extraction called "heappushpop", which is paraphrased below.
A similar function can be defined for popping and then inserting, which in Python is called "heapreplace": Finding an arbitrary element takes O(n) time.
Decrease key can be done as follows: Increase key can be done as follows: Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element.
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.
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.
The exact value of the above (the worst-case number of comparisons during the heap construction) is known to be equal to: where s2(n) is the sum of all digits of the binary representation of n and e2(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 log2n + O(1) comparisons.
[10][11] 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.
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.
Specifically, sometimes the root is placed at index 1, in order to simplify arithmetic.
When a dynamic array is used, insertion of an unbounded number of items is possible.
Let j be the index of the largest child of a[i] (for a max-heap, or the smallest child for a min-heap) 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.)
The sift-down function is applied tail-recursively to index j until the heap property is established for all elements.
The index value where it is working doubles in each iteration, so that at most log2 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.
The view also presents a new and conceptually simple algorithm for merging heaps.
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.
Every non-root node is either the left or right child of its parent, so one of the following must hold: Hence, Now consider the expression
Therefore, irrespective of whether a node is a left or right child, its parent can be found by the expression: 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 array-based heap, simply swapping the children might also necessitate moving the children's sub-tree nodes to retain the heap property.
