Scene 1

Introduction to Heap Sort. ADVANCED DATA STRUCTURES. 

Scene 2

Heap Sort is a comparison-based sorting algorithm based on the Binary Heap data structure.
It is an optimized version of selection sort.
The algorithm repeatedly finds the maximum (or minimum) element and swaps it with the last (or first) element.
Using a binary heap allows efficient access to the max (or min) element in O(log n) time instead of O(n).
The process is repeated for the remaining elements until the array is sorted.

Heap Sort Algorithm. ADVANCED DATA STRUCTURES. First convert the array into a max heap using heapify, Please note that this happens in-place. The array elements are re-arranged to follow heap properties. Then one by one delete the root node of the Max-heap and replace it with the last node and heapify. Repeat this process while size of heap is greater than 1.
Time Complexity: O(n log n). 

Scene 3

First convert the array into a max heap using heapify, Please note that this happens in-place. 
The array elements are re-arranged to follow heap properties. 
Then one by one delete the root node of the Max-heap and replace it with the last node and heapify. 
Repeat this process while size of heap is greater than 1.
Time Complexity: O(n log n)

Heap Sort Working Principle. ADVANCED DATA STRUCTURES. 

Scene 4

Build a Max Heap
Swap root (largest) with last element
Reduce heap size by 1
Heapify root
Repeat until size = 1

Algorithm:
 Heapsort(A) 
BUILD-MAX-HEAP(A)
 for i = A.length downto 2 exchange A[1] with A[i] 
A.heap-size = A.heap-size - 1 
MAX-HEAPIFY(A, 1)

12 14 10 18 23. 18 12 23 10 14. Example. ADVANCED DATA STRUCTURES. 

Scene 5

Let us look at an example array to understand the sort algorithm better −

Building a heap using the BUILD-MAX-HEAP algorithm from the input array −

Rearrange the obtained binary tree by exchanging the nodes such that a heap data structure is formed.

23_to_3. 12 23 10 14 18. 23 12 10 14 18. 23 12 14 10 18. 

Scene 6

14 12 18 10. ADVANCED DATA STRUCTURES. The Heapify Algorithm
Applying the heapify method, remove the root node from the heap and replace it with the next immediate maximum valued child of the root.
The root node is 23, so 23 is popped and 18 is made the next root because it is the next maximum node in the heap.. 

Scene 7

The Heapify Algorithm
Applying the heapify method, remove the root node from the heap and replace it with the next immediate maximum valued child of the root.
The root node is 23, so 23 is popped and 18 is made the next root because it is the next maximum node in the heap.

14. 12 10 ooo. ADVANCED DATA STRUCTURES. Now, 18 is popped after 23 which is replaced by 14.. 

Scene 8

Now, 18 is popped after 23 which is replaced by 14.

The current root 14 is popped from the heap and is replaced by 12.

0000. ADVANCED DATA STRUCTURES. 12 is popped and replaced with 10.. 

Scene 9

Similarly all the other elements are popped using the same process.

oooooo. ADVANCED DATA STRUCTURES. Here the current root element 9 is popped and the elements 8 and 3 are remained in the tree.. 

Scene 10

Here the current root element 9 is popped and the elements 8 and 3 are remained in the tree.

Then, 8 will be popped leaving 3 in the tree.

oooooooa 23. 10 12 18 23. ADVANCED DATA STRUCTURES. 

Scene 11

After completing the heap sort operation on the given heap, the sorted elements are displayed as shown below

Every time an element is popped, it is added at the beginning of the output array since the heap data structure formed is a max-heap. But if the heapify method converts the binary tree to the min-heap, add the popped elements are on the end of the output array.
The final sorted list is,

Implementation. ADVANCED DATA STRUCTURES. #include <stdio.h> void heapify(int[], int); void build_maxheap(int heap[], int n) c = r; }. 

Scene 12

#include <stdio.h>
 void heapify(int[], int); 
void build_maxheap(int heap[], int n)
 c = r; 
}

while (c != 0); 
}
printf("Heap array: ");
 for (i = 0; i < n; i++)
 printf("%d ", heap[i]); 
heapify(heap, n);
 }
 void heapify(int heap[], int n){
 int i, j, c, root, temp;
 for (j = n - 1; j >= 0; j--) {
 temp = heap[0];
 heap[0] = heap[j]; 
// swap max element with rightmost leaf element 
heap[j] = temp; root = 0;

ADVANCED DATA STRUCTURES. do root = c; } while (c < j); } printf("\nThe sorted array is: ");. 

Scene 13

do 
root = c; 
} 
while (c < j); 
} 
printf("\nThe sorted array is: ");

for (i = 0; i < n; i++) 
printf("%d ", heap[i]);
 } 
int main();
 // initialize the array build_maxheap(heap, n); }

Output
Heap array: 4 3 1 0 2 
The sorted array is: 0 1 2 3 4

Advantages of Heap Sort. ADVANCED DATA STRUCTURES. 

Scene 14

Efficient Time Complexity
Minimal Memory Usage
Simplicity
Disadvantages of Heap Sort
Costly
Unstable
Inefficient.

PowerPoint Presentation

Scene 1 (0s)

Scene 2 (4s)

Scene 3 (1m 10s)

Scene 4 (2m 6s)

Scene 5 (2m 50s)

Scene 6 (3m 35s)

Scene 7 (3m 40s)

Scene 8 (4m 26s)

Scene 9 (4m 47s)

Scene 10 (5m 7s)

Scene 11 (5m 32s)

Scene 12 (6m 40s)

Scene 13 (8m 5s)

Scene 14 (9m 21s)