Web
Analytics Made Easy - StatCounter

Binary Heaps (With code in C, C++, and Java)

Introduction

A binary heap is a complete binary tree and possesses an interesting property called a heap property. The heap property states that every node in a binary tree must follow a specific order. There are two types of heaps depending upon how the nodes are ordered in the tree.

  1. max-heap: In max-heap, a parent node is always larger than or equal to its children nodes.
  2. min-heap: In min-heap, a parent node is always smaller than or equal to its children nodes.

Figure 1 shows an example of a max and min heap.

Fig 1: A max-heap (left) and a min-heap (right)

Since binary heap is a complete binary tree, the height of the tree is always O(log n). This is very important because most of the operations we perform in the binary heap scan the tree from top to bottom or bottom to top which leads to complexity of O(log n). This helps us to efficiently implement one sorting algorithm called heap sort and a priority queue.

A binary heap can be efficiently implemented using an array (static or dynamic). To implement a binary heap of height h, we need O(2h) memory blocks and we insert the items in the array following level-order (breadth first) of a tree. Figure 2 shows the array implementation of a tree shown in Figure 1 (left).

Fig 2: An array implementation of a max-heap given in figure 1

The parent, the left child, and the right of a node at i can be calculated as

  • Parent = (i - 1) / 2 (Take floor).
  • Left Child = 2*i + 1
  • Right Child = 2*i + 2

Operations on a binary heap

The various operations on a binary heap are given in detail below. Please note that I am describing the max-heap here but with a little modification this can be changed to min-heap.

Insertion

The new item is initially inserted at the end of the heap (at the last position of the array). If it satisfies the heap property then we are done. Otherwise, we shift it up in the tree as long as it violates the heap property. The algorithm for inserting is given below.

1. Insert the new item at the end of the heap.
2. Compare the newly inserted item with its parent. 
   If the parent is larger, stop. If the parent is smaller,  swap the item with its parent.
3. Repeat step 2 until the parent is larger or equal to the item.

Figure 3 shows the steps of inserting an item in an example heap.

Fig 3: Steps for inserting an item to the heap

In order to insert a new item, in the worst case, we need to travel all the way to the root item. Therefore, the complexity of the insertion operation is O(log n).

Delete Max

In a max heap, the first item is always the maximum. So to delete the maximum, we delete the first item. After the deletion of the first time, we replace the vacant first position by the last time in the array. We might need to shift this item down in order to keep the heap property intact. The algorithm is given below.

1. Store the first time in the tree in some temporary variable.
2. Replace the first node with the item in the last node.
3. Check the first node with its children nodes. 
   If the left child is larger, we swap it with the left child. 
   If the right node is larger, we swap it with the right node. 
4. Repeat step 3 until the parent node is larger than the left and right child node.
5. Return the maximum value (stored in the temporary variable).

Step 3 and 4 in the above algorithm is called a max heapify (or bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down). This step moves the item down in the tree to its appropriate place. Figure 4 shows an example of this process.

Fig 4: An example of a max-heapify process. The item in the first position is shifted down to the tree to its appropriate position.

As the insertion step, the complexity of delete max operation is O(log n).

Building a heap

We can build the heap from an array of n items using two methods. In the first method, we successively perform the insert operation on the heap. In n insert operations, we can build the heap from the array. Since each insert operation takes O(log n) time and there are n such operations, the complexity of this method is O(nlog n).

Another method does this in linear time. In this method, the internal node of the tree is max-heapified one at a time. If there are n items in the array, we start from the item at n/2 position and heapify it and we move to next item and do the same all the way down to the first item in the array. Consider a tree given in figure 5.

Fig 5: The internal nodes are heapified to move them to their appropriate position

There are 10 nodes in the tree. Since the tree is a complete binary tree there are n/2 (floor) leaf nodes. We ignore all the leaf nodes and heapify the internal nodes. Using this method, we can build the heap in linear time O(n). The algorithm for this method is given below.

build-max-heap(arr) {
    n = length of arr;
    for (i = n/2; i > 0; i--) {
        max-heapify(arr, i);
    }
}

Implementation

The implementation of heap in C, C++, and Java is given below.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>

#define MAX_SIZE 15

// returns the index of the parent node
int parent(int i) {
return (i - 1) / 2;
}

// return the index of the left child
int left_child(int i) {
return 2*i + 1;
}

// return the index of the right child
int right_child(int i) {
return 2*i + 2;
}

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

// insert the item at the appropriate position
void insert(int a[], int data, int *n) {
if (*n >= MAX_SIZE) {
printf("%s\n", "The heap is full. Cannot insert");
return;
}
// first insert the time at the last position of the array
// and move it up
a[*n] = data;
*n = *n + 1;


// move up until the heap property satisfies
int i = *n - 1;
while (i != 0 && a[parent(i)] < a[i]) {
swap(&a[parent(i)], &a[i]);
i = parent(i);
}
}

// moves the item at position i of array a
// into its appropriate position
void max_heapify(int a[], int i, int n){
// find left child node
int left = left_child(i);

// find right child node
int right = right_child(i);

// find the largest among 3 nodes
int largest = i;

// check if the left node is larger than the current node
if (left <= n && a[left] > a[largest]) {
largest = left;
}

// check if the right node is larger than the current node
if (right <= n && a[right] > a[largest]) {
largest = right;
}

// swap the largest node with the current node
// and repeat this process until the current node is larger than
// the right and the left node
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest, n);
}

}

// converts an array into a heap
void build_max_heap(int a[], int n) {
int i;
for (i = n/2; i >= 0; i--) {
max_heapify(a, i, n);
}
}

// returns the maximum item of the heap
int get_max(int a[]) {
return a[0];
}

// deletes the max item and return
int extract_max(int a[], int *n) {
int max_item = a[0];

// replace the first item with the last item
a[0] = a[*n - 1];
*n = *n - 1;

// maintain the heap property by heapifying the
// first item
max_heapify(a, 0, *n);
return max_item;
}

// prints the heap
void print_heap(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d\n", a[i]);
}
printf("\n");
}


int main() {
int n = 10;
int a[MAX_SIZE];
a[1] = 10; a[2] = 12; a[3] = 9; a[4] = 78; a[5] = 33; a[6] = 21; a[7] = 35; a[8] = 29; a[9] = 5; a[10] = 66;
build_max_heap(a, n);
insert(a, 55, &n);
insert(a, 56, &n);
insert(a, 57, &n);
insert(a, 58, &n);
insert(a, 100, &n);
print_heap(a, n);
return 0;
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// C++ implementation of a binary heap

#include <iostream>
using namespace std;

class BinaryHeap {
private:
const static int MAX_SIZE = 15;
int heap[MAX_SIZE];
int size;

public:
BinaryHeap() {
size = 0;
}

// returns the index of the parent node
static int parent(int i) {
return (i - 1) / 2;
}

// return the index of the left child
static int leftChild(int i) {
return 2*i + 1;
}

// return the index of the right child
static int rightChild(int i) {
return 2*i + 2;
}


static void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

// insert the item at the appropriate position
void insert(int data) {
if (size >= MAX_SIZE) {
cout<<"The heap is full. Cannot insert"<<endl;
return;
}

// first insert the time at the last position of the array
// and move it up
heap[size] = data;
size = size + 1;


// move up until the heap property satisfies
int i = size - 1;
while (i != 0 && heap[BinaryHeap::parent(i)] < heap[i]) {
BinaryHeap::swap(&heap[BinaryHeap::parent(i)], &heap[i]);
i = BinaryHeap::parent(i);
}
}

// moves the item at position i of array a
// into its appropriate position
void maxHeapify(int i){
// find left child node
int left = BinaryHeap::leftChild(i);

// find right child node
int right = BinaryHeap::rightChild(i);

// find the largest among 3 nodes
int largest = i;

// check if the left node is larger than the current node
if (left <= size && heap[left] > heap[largest]) {
largest = left;
}

// check if the right node is larger than the current node
// and left node
if (right <= size && heap[right] > heap[largest]) {
largest = right;
}

// swap the largest node with the current node
// and repeat this process until the current node is larger than
// the right and the left node
if (largest != i) {
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
maxHeapify(largest);
}

}

// returns the maximum item of the heap
int getMax() {
return heap[0];
}

// deletes the max item and return
int extractMax() {
int maxItem = heap[0];

// replace the first item with the last item
heap[0] = heap[size - 1];
size = size - 1;

// maintain the heap property by heapifying the
// first item
maxHeapify(0);
return maxItem;
}

// prints the heap
void printHeap() {
for (int i = 0; i < size; i++) {
cout<<heap[i]<<endl;
}
cout<<endl;
}
};

int main() {
BinaryHeap heap;
return 0;
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Java implementation of a binary heap

class BinaryHeap {
private static final int MAX_SIZE = 15;
private int [] heap;
private int size;

public BinaryHeap() {
heap = new int[MAX_SIZE];
size = 0;
}

// returns the index of the parent node
public static int parent(int i) {
return (i - 1) / 2;
}

// return the index of the left child
public static int leftChild(int i) {
return 2*i + 1;
}

// return the index of the right child
public static int rightChild(int i) {
return 2*i + 2;
}

// insert the item at the appropriate position
public void insert(int data) {
if (size >= MAX_SIZE) {
System.out.println("The heap is full. Cannot insert");
return;
}

// first insert the time at the last position of the array
// and move it up
heap[size] = data;
size = size + 1;


// move up until the heap property satisfies
int i = size - 1;
while (i != 0 && heap[BinaryHeap.parent(i)] < heap[i]) {
int temp = heap[i];
heap[i] = heap[parent(i)];
heap[parent(i)] = temp;
i = BinaryHeap.parent(i);
}
}

// moves the item at position i of array a
// into its appropriate position
public void maxHeapify(int i){
// find left child node
int left = BinaryHeap.leftChild(i);

// find right child node
int right = BinaryHeap.rightChild(i);

// find the largest among 3 nodes
int largest = i;

// check if the left node is larger than the current node
if (left <= size && heap[left] > heap[largest]) {
largest = left;
}

// check if the right node is larger than the current node
// and left node
if (right <= size && heap[right] > heap[largest]) {
largest = right;
}

// swap the largest node with the current node
// and repeat this process until the current node is larger than
// the right and the left node
if (largest != i) {
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
maxHeapify(largest);
}

}

// returns the maximum item of the heap
public int getMax() {
return heap[0];
}

// deletes the max item and return
public int extractMax() {
int maxItem = heap[0];

// replace the first item with the last item
heap[0] = heap[size - 1];
size = size - 1;

// maintain the heap property by heapifying the
// first item
maxHeapify(0);
return maxItem;
}

// prints the heap
public void printHeap() {
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}

public static void main(String [] args) {
BinaryHeap heap = new BinaryHeap();
}
}