Binary Heaps Notes For GATE

Binary Heap is an important topic belonging to the famous chapter of Computer Science i.e. Data Structure. And, when it comes to a competitive examination like GATE, you have to read the whole topic quite deeply. In this article, we have covered all the topics relevant to the binary heap. We hope the notes for the CSE topics will help you understand this topic in a better way.

Topic of Contents

• What are Binary Heaps?
• Types of Binary Heaps
• How is Binary Heap represented?
• Heap Tree Construction
• Basic Operations In Binary Heaps
• Video on Binary Heap
• Advantages of Heap
• Disadvantages of Heap
• Practice Problems – Binary Heap

What are Binary Heaps?

Binary heap is a data structure. It is like a binary tree in which every node has at most two children at the most. Binary heaps are a standard way of executing priority queues. It was organized by J. W. J. Williams in 1964 as a data structure for heapsort.

Types of Heaps

There are two types of heaps:

1. Max Heap
2. Min Heap
3. Max Heap: A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.

In this picture you can see that the root element has maximum value, which means in the max heap the root element is always greater.

NOTE: This is very important, in the max heap, the parent value should always be greater than a child node at every level.

1. Min Heap: In a Min-Heap the key present at the root node must be less than or equal among the keys present at all of its children.

In this picture, you can see that the root element has minimum value, which means in the min heap the root element is always minimum.

NOTE: This is very important, in the min heap, the parent value should always be smaller than a child node at every level.

How is Binary Heap Represented?

A Binary Heap is like a complete Binary Tree. It is commonly represented as an array.

Figure: Representation of Binary Heap

Heap Tree Construction:

When it comes to constructing a heap tree, we can follow two methods:

1. 1. Insert key one by one in the given order

O(nlogn) – Time complexity

Where O is order and n is element

1. Heapify Method

O(n) – Time complexity

Where O is order and n is element

When it comes to creating a heap tree (Min Heap or Max Heap), the heapify method is most suitable, because it takes less time as compared to the other methods.

Explanation of Picture

In this example we have used Heapify method:

Heapify → It is a method to rearrange the heap to sustain heap property.

In the above picture, we have a set of arrays and we have to create a Max heap from that. Whenever we have to create a tree, we have to start from the left side. We have created a basic tree that you can see in the picture as “Initial Elements”.

Now, to create a max heap, we have to keep one thing in mind that the parent node should be greater than the child node at every level. If you noticed, the second level 3 is a parent node and 8 is a child node. Here, the parent node is smaller than the child node, so we have to swap them. Once we swap, 8 will take the position of 3.

Now the main parent node has 4 values which are smaller than the child value, we again play swap games and this way we can get the greater value in the main parent node.

Basic Heap Operations

• Insertion → Add a new item to the heap.
• Deletion → Delete an item from the heap.

Insertion: Firstly, we have to insert the new element at the end of the heap and we always start from the left side. After inserting the node, we have to analyze the heap property as the new elements can affect the sequence. We will apply a heapify method to create a proper heap. You can create a Max or Min heap according to your preference or the question asked in the exam.

Deletion: In the deletion process, we replace the element to be removed by the last rightmost element in the heap. After placing the last element in place of the deleted one, we have to check whether the heap is following the property of the heap or not. If not, we have to set it according to the heapify method.

Video on Binary Heap

Advantages of Heap

1. Heap data structure preferred graph algorithms.

2. It helps in finding the maximum and minimum elements.

3. Heap is extensively accepted because it is very effective.

4. The Heap method is also used in the Priority Queue.

5. It allows you to access variables globally.

6. Heap doesn’t have any limit on memory size.

NOTE: The major advantage of the binary heap is that you can add new values to it efficiently after initially constructing it.

Disadvantages of Heap

• It can provide the maximum memory an OS can provide.
• It takes more time to compute.
• Memory management is more complicated in heap memory as it is used globally.
• It takes too much time in execution compared to the stack.

Practice Problem – Heap

Q. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

(A) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35

(B) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15

(C) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15

(D) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Q. A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

(A)

(B)

(C)

(D)

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.

Also Explore,

• Introduction to Data structures
• Introduction to Array Notes
• Linked Lists Notes
• Heap Sort Notes
• Binary Search Trees Notes
• AVL Trees Notes
• Graphs and their Applications
• Trees
• Stacks and their Applications
• Queues Notes
• Introduction to Recursion
• Heap Sort Notes For GATE
• Decimal to Binary Conversion
• Binary Search Trees