Scribd
Upload
6 views4 pages

Heap Sort Algorithm Explained

Heap sort is an algorithm that sorts elements by creating a min-heap or max-heap from the given array. The process involves constructing a binary tree, transforming it into a max heap, and repeatedly deleting the root element while adding it to the sorted list until the heap is empty. The time complexity for all cases (best, average, and worst) is O(n log n).

Uploaded by

middenchopra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views4 pages

Heap Sort Algorithm Explained

Heap sort is an algorithm that sorts elements by creating a min-heap or max-heap from the given array. The process involves constructing a binary tree, transforming it into a max heap, and repeatedly deleting the root element while adding it to the sorted list until the heap is empty. The time complexity for all cases (best, average, and worst) is O(n log n).

Uploaded by

middenchopra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Heap Sort

Heap sort processes the elements by creating the min-heap or max-heap using the
elements of the given array. Min-heap or max-heap represents the ordering of array in
which the root element represents the minimum or maximum element of the array.

Heap sort basically recursively performs two main operations -

o Build a heap H, using the elements of array.


o Repeatedly delete the root element of the heap formed in 1st phase.

Step by Step Process


The Heap sort algorithm to arrange a list of elements in ascending order is performed using following
steps...

 Step 1 - Construct a Binary Tree with given list of Elements.


 Step 2 - Transform the Binary Tree into Max Heap.
 Step 3 - Delete the root element from Max Heap using Heapify method.
 Step 4 - Put the deleted element into the Sorted list.
 Step 5 - Repeat the same until Heap becomes empty.
 Step 6 - Display the sorted list.

Heap sort complexity

Case Time Complexity

Best Case O(n logn)

Average Case O(n log n)

Worst Case O(n log n)

You might also like