Scribd
Upload
8 views13 pages

Heap Sort

heap sort notes dsa with example sem 3

Uploaded by

Mayank Sharma
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
8 views13 pages

Heap Sort

heap sort notes dsa with example sem 3

Uploaded by

Mayank Sharma
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
You are on page 1/ 13

Data Structures

Topic:HEAP
-SORT

By- Mohit Dayma and


Mayank Kumar Sharma
B.Tech CSE-B
What is Heap Sort?
Heap Sort is a sorting algorithm that uses a binary heap data
structure. It transforms the list into a heap, allowing for efficient
sorting
It's known for its in-place sorting capabilities.
sorts items within the original array, using only a small amount of extra space

The algorithm operates in two main phases:


1- building the heap
2- sorting the elements.
How does Heap Sort Works?
Heap Sort operates by first building a max heap from the input
data.

Once the max heap is created, the largest element is swapped with
the last element, reducing the heap size.

This process is repeated until the entire list is sorted.


How does Heap Sort Works?
30
BUILDING THE HEAP
This is done by arranging the 15 5
elements in a way that
satisfies the heap property.
For a max heap, each parent 8 10
node is greater than or equal
to its child nodes.
MAX HEAP
This ensures that the largest
element is always at the root.
a[0]
How does Heap Sort Works? 30
Example a[2]
Step1- largest element is swapped a[1] 15 5
with the last element, reducing the
heap size.[30 swapped from 10 and
size of heap reduced.] 8 10
a[3] a[4]

a[0] a[1] a[2] a[3] a[4]

Array a[].
a[0]
How does Heap Sort Works? 10
Example a[2]
Step 2- The heapify process is a[1] 15 5
crucial for maintaining the heap
structure. It involves adjusting the
positions of elements to ensure the 8
a[3]
heap property is preserved after a
swap.
[10 and 15 will be swapped to preserve
the property of max heap]

a[0] a[1] a[2] a[3] a[4]

Array a[].
a[0]
How does Heap Sort Works? 15
Example a[2]
Step 3- same steps will be repeated a[1] 10 5
till we get the sorted array a[].
8
[swapping of 8 and 15 reducing the a[3]
heap size

a[0] a[1] a[2] a[3] a[4]

Array a[].
How does Heap Sort Works?
Example-
a[0] a[0]
heapify
8 10
a[2] a[2]
a[1] 10 5 a[1] 8 5

a[0] a[1] a[2] a[3] a[4]


Array a[].
Array a[].
How does Heap Sort Works?
Example-
a[0] a[0]
heapify
5 8 swapped

a[1] 8 a[1] 5

a[0] a[1] a[2] a[3] a[4]


Array a[].
Array a[].
How does Heap Sort Works?
Example-
a[0]

Sorted
array a[].

a[0] a[1] a[2] a[3] a[4]

Array a[].
Complexity
Heap Sort has a Time complexity of O(n log n) in
the average and worst cases.
The building of the heap takes O(n) time, while the
sorting process requires O(log n) time for each
element.
This makes Heap Sort efficient for large datasets.
Its Space complexity of O(1). This means it sorts
the elements in place without needing additional
storage for another array.
Disadvantages of Heap Sort
Despite its strengths, Heap Sort has drawbacks,
such as being not stable, which means that equal
elements may not retain their original order.
Additionally, its constant factors can make it
slower than other algorithms like quick-sort for
smaller datasets.
THANK YOU

You might also like