Heap Sort Notes For GATE

Heap Sort is an important topic belonging to the Data Structure family. And, when it comes to a competitive examination like GATE, you have to read this whole topic quite deeply. In this article we have covered all the topics relevant to the linked list. We hope the notes for the CSE topics will help you understand this topic in a better way.

Topic of Contents

• What Is Heapsort?
• What Is Heap Data Structure?
• How To Heapify A Tree?
• How To Heapify Root Element When Its Subtrees Are Already Max Heaps?
• Working Of Heap Sort
• FAQs Related To Heap Sort

What is Heapsort?

Heapsort is a popular terminology that belongs to the heap data structure family. It is a comparison-based sorting method based on Binary Heap data structure. In heapsort, we generally prefer the heapify method to sort the elements.

To learn Heapsort in-depth, we need to learn about arrays and trees first.

The connection between Array Pointers and Tree Elements

A complete binary tree is allowing us to find the children and parents of any node.

The above picture shows the strong relationship between arrays and trees and how we can sort an array in a form of heap.

What is Heap Data Structure?

Heap is a special data structure. It has a tree structure. A heap data should follow some properties, then only we can consider it a genuine heap data structure. The properties are:

• It should be a complete binary tree.
• It should be either max-heap or min-heap. In short, it should follow all the properties of a binary heap tree.

How to “heapify” a tree?

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 like Insert key one by one in the given order.

This is the case of Max heap because in this above picture the parent node is greater than the child node. And to perform the heapify method, we have to compare the nodes and swap them if required.

How to heapify root element when its subtrees are already max heaps?

Now we need to heapify the above tree, here we go:

To maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.

Working of Heap Sort

1. If it is about the max heap, then the highest element is stored at the root node.
2. Swap: Extract the root element and we need to place the last element of the tree (heap) at the vacant place.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root element again so that we have the highest element at root.
5. The process is repeated until all the items of the list are sorted.

In the above picture, we are representing all the operations. And we are trying to balance a tree by heapify method.

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
• Binary Heaps Notes
• Binary Search Trees Notes
• AVL Trees Notes
• Graphs and their Applications
• Trees
• Stacks and their Applications
• Queues Notes
• Introduction to Recursion
• Decimal to Binary Conversion
• Binary Search Trees
• Binary Heaps Notes For GATE