Binary Heap
A binary heap is a heap, i.e, a tree which obeys the property that the root of any tree is greater (or smaller) than 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 bottom most level is completely filled.
 MaxHeap Property: The key of every node is larger than its children.
Notice that the binary tree does not enforce any ordering between the sibling nodes. And also notice that the completeness of the tree ensures that the height of the tree is \(\lfloor \lg n \rfloor\), where \(n\) is the number of elements in the heap.
A binary heap in which every node is smaller than 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 \(\lfloor \frac{n}{2} \rfloor\).
To understand this, consider the numbering in the nodes below:
For the sake of simplicity, we keep the 0th 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 it's parent, then it's okay.
 Otherwise, exchange the key with it's 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, so 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:
 Arbitarily 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 it's 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 
