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.

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 CriteriaGATE 2023GATE Admit CardGATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Also Explore,

Leave a Comment

Your Mobile number and Email id will not be published.

*

*