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.

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 \(\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 min-heap. We'll explore max-heaps in this wiki but min-heaps are just as simple.

A Max Heap

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.

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?

1. If the new key is still smaller than its parent, then it's okay.
2. 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.

A better way to build a max heap is this:

1. Arbitrarily position the keys.
2. 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.

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:

1. Swap the element at the extreme end of the heap with the root.
2. Remove the value at the extreme end and return it as the maximum value.
3. 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.

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:

1. Build a max heap of the elements you want to sort.
2. Create an empty array and successively fill the array with extractMax successively run on the heap.
3. 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.

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

#max-heap implementation
class BinaryHeap:

    #for the sake of simplicity let us keep the 0th node unused
    tree = [0]

    #and let us define the self.left and right childs and the parent
    left = lambda self,n: 2*n
    right = lambda self,n: 2*n + 1
    parent = lambda self,n: n/2

    def increaseKey(self,index,key):
        assert self.tree[index] < key

        #Change the value
        self.tree[index] = key

        #and float up
        while index > 1 and self.tree[self.parent(index)] < self.tree[index]:
            self.tree[self.parent(index)], self.tree[index] = self.tree[index], self.tree[self.parent(index)]
            index = self.parent(index)

    def insert(self, key):

        #add -infinity to the end of the tree
        self.tree.append(-float("inf"))

        #and float increase it back to key
        self.increaseKey(len(self.tree)-1,key)

    def maxHeapify(self, index):
        while (self.left(index) < len(self.tree) and self.tree[index] < self.tree[self.left(index)]) or \
        (self.right(index) < len(self.tree) and self.tree[index] < self.tree[self.right(index)]):

            #pulling up the larger node makes sense
            if self.right(index) >= len(self.tree) or self.tree[self.left(index)] > self.tree[self.right(index)]:
                self.tree[index], self.tree[self.left(index)] = self.tree[self.left(index)], self.tree[index]
                index = self.left(index)
            else:
                self.tree[index], self.tree[self.right(index)] = self.tree[self.right(index)], self.tree[index]
                index = self.right(index)

    def getMax(self):
        assert len(self.tree) > 1
        return self.tree[1]

    def extractMax(self):
        result = self.getMax()

        #swap the first element with the last element
        self.tree[1] = self.tree[len(self.tree)-1]

        #remove the last element and sink the root down to the appropriate place
        self.tree.pop()
        self.maxHeapify(1)

        return result

    def heapSort(self):
        sortedElements = []

        #apply extractMax repeatedly
        while len(self.tree) > 1:
            sortedElements.append(self.extractMax())

        #flip the array and return
        sortedElements.reverse()
        return sortedElements

    #how to build a max heap
    def __init__(self, arr=[]):
        self.tree = [0] + arr

        #apply maxHeapify from the bottom
        for index in range((len(self.tree)-1)/2,1,-1):
            self.maxHeapify(index)

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

void Heap::heapSort(int* array,int numberOfElementsInArray)
{
 //in for loop we will take each element of array and 
//put it in it's spot inside heap, which we will presume to be empty 
for( int i=0; i<numberOfElementsInArray; i++)
 {
    this->insertNode(array[i]); //call of member function to insert each element into max heap
 }

//then we will use function deleteRoot which returns the root of a Heap, 
//and sorts heap afterwards so it always gives us max element and put 
//those elements in our array so we get array in a  non-decreasing order

int i =0;
while( ! this->isEmpty() )
{
   array[i] = this->deleteRoot();
  i++;
}
//now in this array we have elements from maximum element to minimum, 
//there we have it array sorted in non-decreasing order.
}

//implementation of deleteRoot() function

int Heap::deleteRoot()
{
  //bear in mind that this heap is implemented as an array, a static not dynamic structure

if( this->numberOfElements == 0)            //numberOfElements of a given heap
    throw new Exception("The heap is empty");
int result = this->heap[1];                            //heap is an array that holds elements of our heap, and 
                                                                    //heap[1] is the root of our heap, so we save it  
                                                                    //because with this algorithm we will overwrite it
int last = this->heap[numberOfElements];   
numberOfElements--;
int i = 1;
while (2* i <numberOfElements+1) //sorting the heap
{
          int child = 2*i;      //read up on binary static heaps in order to understand this part
          if ( child + 1 < nuberOfElements + 1 && heap[child + 1] < heap[child])
                                   child = child +1;
          if (last <= heap[child]) 
                            break;
          heap[i] = heap[child];
          i = child;
}
heap [i] = last; 
return result; //root
}