The binary heap is a binary tree (a tree in which each node has at most two children) which satisfies the following additional properties:
- The binary tree is complete, i.e. every level except the bottom-most level is completely filled and nodes of the bottom-most level are positioned as left as possible.
- Max-heap property: The key of every node is larger than or equal to its children.
Notice that the binary tree does not enforce any ordering between the sibling nodes. Also notice that the completeness of the tree ensures that the height of the tree is where is the number of elements in the heap.
A binary heap in which every node is smaller than or equal to their children is called a min-heap. We'll explore max-heaps in this wiki but min-heaps are just as simple.
One simple implementation hack is to store the list in a tree, with the left child of every node numbered being and the right child being . Thus, the parent of any node is .
To understand this, consider the numbering in the nodes below:
For the sake of simplicity, we keep the index unused.
To begin with, let us assume that we already have a binary heap. How should we deal with it when the key at a known index is increased?
- If the new key is still smaller than its parent, then it's okay.
- Otherwise, exchange the key with its parent's key (float up). Keep floating up until the key reaches a position good enough.
For insertion, we append a value to the end of the binary tree and then float it up, as long as necessary. This is exactly the same as
Let us see how we insert 46 into this heap.
Building a Heap
Building a heap is now simple. All we do is repeatedly insert keys starting with the empty heap.
However, there is a better way, as we shall see next.
Both these operations at worst traverse the full height of the tree, taking time in . Building a heap as we discussed takes ) time.
A better way to build a max heap is this:
- Arbitrarily position the keys.
- For all the nodes starting from the lowest level to the top, run
This works because the subtrees with just one key are already heaps and we're building heaps along the way.
You can help by adding the proof.
Given an array of elements, the above algorithm arranges them into a max heap in time.
Assume that there is a binary tree whose root isn't properly placed but everything else is intact, i.e. both the left and right subtrees are perfect binary heaps but the root does not satisfy the heap property. How would you arrange the root node in its perfect position? By sinking it down, of course!
Swap the node in question with the larger (think why!) of its two children and keep swapping until it reaches a position where it is either larger than its children or is a leaf node (childless).
This procedure is called
extractMax returns and removes the node with the largest key in the heap. Here is how we do it:
- Swap the element at the extreme end of the heap with the root.
- Remove the value at the extreme end and return it as the maximum value.
- Sink in the root to the right place with
Like insertion, the worst thing that could happen here is traversal of the entire height. Hence, these operations run in as well.
Main Article: Heap Sort
Notice that each time we run
extractMax, we get the next maximum key in the heap. This gives us a very simple sorting algorithm:
- Build a max heap of the elements you want to sort.
- Create an empty array and successively fill the array with
extractMaxsuccessively run on the heap.
- Reverse the array.
This takes time.
The heapsort is not exclusive to binary heaps only; all kinds of heaps can be effectively used.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
Let us presume we already have built class heap that models max heap and is implemented as an array of elements. Also, let's presume that, as an input to our function (we'll call it heapsort), we have an array of unsorted elements, which we need to sort.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50