Binary Heap
A binary heap is a heap, i.e, a tree which obeys the property that the root of any tree is greater than or equal to (or smaller than or equal to) all its children (heap property). The primary use of such a data structure is to implement a priority queue.
Contents
Structure
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 bottommost level is completely filled and nodes of the bottommost level are positioned as left as possible.
 Maxheap 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 \(\big\lfloor \log n \big\rfloor,\) where \(n\) 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 minheap. We'll explore maxheaps in this wiki but minheaps are just as simple.
One simple implementation hack is to store the list in a tree, with the left child of every node numbered \(n\) being \(2n\) and the right child being \(2n + 1\). Thus, the parent of any node is \(\big\lfloor \frac{n}{2} \big\rfloor\).
To understand this, consider the numbering in the nodes below:
For the sake of simplicity, we keep the \(0^\text{th}\) index unused.
Increase Key and Insertion
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.
Insertion
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 increaseKey
.
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.
Complexity
Both these operations at worst traverse the full height of the tree, taking time in \(O(\lg n)\). Building a heap as we discussed takes \(O(n \lg n\)) time.
Building a Heap
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
maxHeapify
.
This works because the subtrees with just one key are already heaps and we're building heaps along the way.
Complexity
You can help by adding the proof.
Given an array of \(n\) elements, the above algorithm arranges them into a max heap in \(O(n)\) time.
Max Heapify and Extraction
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 maxHeapify
.
Extraction
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
maxHeapify
.
Complexity
Like insertion, the worst thing that could happen here is traversal of the entire height. Hence, these operations run in \(O(\lg n)\) as well.
Heapsort
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
extractMax
successively run on the heap.  Reverse the array.
This takes \(O(n \lg n)\) time.
The heapsort is not exclusive to binary heaps only; all kinds of heaps can be effectively used.
Example Implementation
Python
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 

C++
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 
