What does a Binary Heap do?

Last Updated on September 22, 2023 by Mayank Dham

In this article, we will learn what a binary heap is, how a binary heap is represented, what operations can be performed on a binary heap, and what are the applications of a binary heap.

What is a Binary Heap?

In a binary heap, data is represented in the form of a binary tree. Below are some properties of the binary heap which make it different from the binary tree.

• Binary heaps are the complete binary tree. The complete binary tree is a tree in which all the levels are completely filled except the last level and in the last level, all the keys are as left as possible. This property is useful to make sorted in an array.

Types of Binary Heap

• There are two types of binary heap, min heap and max heap.

Min Heap: the value of the root node must be smaller than the values of the other node in the binary heap.

Max Heap: the value of the root node must be greater than the values of the other nodes in the binary heap.

How a Binary Heap is Represented?

An array data structure is used to represent a binary heap. Let’s see how a binary heap is represented in an array data structure.

• The root element will be stored at array[0].
• To store other nodes below are some indexes to store that element. Lets see what are indexes of to store node are at the ith index.
  • Array[(2*i)+1] points to the left child of the ith node.
  • Array[(2*i)+2] points to the right child of the ith node.
  • Array[(i-1)/2] points to the parent of the ith node.

Lets take an example and see how a binary heap is stored in an array.

In the above example, we can see that the root element is at position 0 in an array. Now, we can see that the left child (30) is at position 1 (20+1 = 1) and the right child (60) is at position 2 (20+2 = 2). Now, we can use the same approach to find the remaining positions.

Different Operations on a Min Heap:

Let’s see what kind of various operations can be performed on a min-heap.

getMin(): This operation returns the minimum element from the min heap. The Min element of the min heap will be an array[0].

Time complexity: O(1) we can access the 0th element in O(1) time.

extractMin(): This operation removes the minimum element from the min heap.

Time Complexity: O(logn) after removing the root element (min element ) from the min heap, we need to call the heapify() function to maintain the property of the binary heap.

decreaseKey(): This function is used to perform a decrement on the key.

Time Complexity: O(n) if the value of the current node is greater than the parent node then we do not need to do anything. If it is not the above case then, to fix the heap property we need to traverse the min heap.

insert(): This function is used to add a new element in the min heap.

Time complexity: O(logn) first, we insert a new node at the end of the binary heap. If the newly inserted node is greater than its parent node then we do not need to do anything. Else, we have to find an appropriate position for the new node and this takes O(logn) time.

delete(): This function is used to delete a node from the min heap.

Time Complexity: O(logn) we will use decreaseKey() function to replace the deleted with the minimum infinite. After performing this, we need to make sure that the minimum infinite must reach the root. So after that, we can call extractMin() to remove that key.

We understood all the operations, now lets see how to write a program to perform all the operations.

Code Implementation

Output

20
40
10

Applications of the Binary Heap:

Below are some important applications of the binary heap:

• The binary heap is used by heap sort to perform heap sort on an array in O(n*logn) time.
• The binary heap is used to perform the priority queue efficiently because the binary heap provides functions such as insert, delete, extract min, and decrease keys.
• Variations of the binary heap such as the Binomial heap and Fibonacci heap are used to perform union effectively.
• The priority queue ( implemented using the binary heap) is used to perform in the implementation of the various graph algorithms such as Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.

FAQs Related to Binary Heap

1) What is the main difference between min-heap and max-heap?
In the min-heap, the root element is always less than its left child and right child. While, in the max-heap, the root element is always greater than its left child and right child.

2) What is the heapify function in the binary heap?
The heapify function is used to perform reordering on the binary heap so that the binary tree follows the property of the min heap or max heap. The heapify function works in O(logn) time complexity.

3) What types of problems can be solved using the binary heap?
Below are some famous problems which can be solved using the binary heap.

• Merge K sorted arrays.
• Kth largest element in an array
• Sort an almost sorted array