Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

Chapter 2:
Sorting Algorithm
- Heap Sort
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

Basic Idea of Heap Sort

Example
Complexity of Heap Sort

HEAP SORT
2
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

 Basic idea to know:

 1. Array representation of Binary Tree
 2. Complete Binary Tree  no missing
element in the tree
 3. Heap sort

MAIN IDEA
3
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

 Themain objective: To sort the array in

increasing order
 Improved version of binary tree
 Need to do:
 1. Build the heap based on Max Heap
 2. Sort the heap using heapify procedure

IDEA
4
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

GET TO KNOW THE MAIN IDEA

 1. Array representation of Binary Tree
 [Link] Binary Tree  no missing
element in the tree
15 19 10 7 17 16
[0] [1] [2] [3] [4] [5]
15
Rules of BT:
If node at index I
19 10 Its left child is at 2i+1
Its right child is at 2i+2
Its parent is at [i/2]
7 17 16
5
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

15 19 10 7 17 16
[0] [1] [2] [3] [4] [5]

15 Steps:
1. At the first element (i=0), become a parent
2. Check its left child (i=1), and right child (i=2)
19 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

6
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

15 19 10 7 17 16
[0] [1] [2] [3] [4] [5]

15 Steps:
1. At the first element (i=0), become a parent
2. Check its left child (i=1), and right child (i=2)
19 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

7
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

15 19 10 7 17 16
[0] [1] [2] [3] [4] [5]

15 Steps:
1. At the first element (i=0), become a parent
2. Check its left child (i=1), and right child (i=2)
19 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

8
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 15 10 7 17 16
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the first element (i=0), become a parent
2. Check its left child (i=1), and right child (i=2)
15 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

9
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 15 10 7 17 16
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the next element (i=1), become a parent
2. Check its left child (i=3), and right child (i=4)
15 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

10
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 15 10 7 17 16
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the next element (i=1), become a parent
2. Check its left child (i=3), and right child (i=4)
15 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 17 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

11
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 17 10 7 15 16
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the next element (i=1), become a parent
2. Check its left child (i=3), and right child (i=4)
17 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 15 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

12
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 17 10 7 15 16
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the next element (i=2), become a parent
2. Check its left child (i=5), and right child (i=4)
17 10 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 15 16 6. Repeat the step 1 until 5 for the next parent
until reach the last element

13
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 1. Build the heap  max heap, parent must greater than child

19 17 16 7 15 10
[0] [1] [2] [3] [4] [5]

19 Steps:
1. At the next element (i=2), become a parent
2. Check its left child (i=5), and right child (i=4)
17 16 3. Compare the child, select the greater child
4. Compare that child with parent
5. If the child greater than parent, swap it
7 15 10 6. Repeat the step 1 until 5 for the next parent
until reach the last element

14
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

19 17 16 7 15 10
[0] [1] [2] [3] [4] [5]

19 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
17 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 10 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 15
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

19 17 16 7 15 10
[0] [1] [2] [3] [4] [5]
Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
17 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 10 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 16
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

19 10 17 16 7 15
[0] [1] [2] [3] [4] [5]

10 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
17 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 17
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 17 16 7 15 19
[0] [1] [2] [3] [4] [5]

10 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
17 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 18
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 17 16 7 15 19
[0] [1] [2] [3] [4] [5]

10 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
17 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 19
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

17 10 16 7 15 19
[0] [1] [2] [3] [4] [5]

17 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=5) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=5), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 20
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

17 10 16 7 15 19
[0] [1] [2] [3] [4] [5]

17 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 21
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

17 10 16 7 15 19
[0] [1] [2] [3] [4] [5]
Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 15 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 22
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

17 15 10 16 7 19
[0] [1] [2] [3] [4] [5]

15 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 23
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 10 16 7 17 19
[0] [1] [2] [3] [4] [5]

15 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 24
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 10 16 7 17 19
[0] [1] [2] [3] [4] [5]

15 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 16 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 25
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

16 10 15 7 17 19
[0] [1] [2] [3] [4] [5]

16 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 26
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

16 10 15 7 17 19
[0] [1] [2] [3] [4] [5]

16 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=4) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=4), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 27
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

16 10 15 7 17 19
[0] [1] [2] [3] [4] [5]
Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
7 4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 28
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

16 7 10 15 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 29
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 30
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 15 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 31
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 10 7 16 17 19
[0] [1] [2] [3] [4] [5]

15 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 7 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 32
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 10 7 16 17 19
[0] [1] [2] [3] [4] [5]

15 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=3) and insert into
10 7 the empty node
3. Store the deleted element in the last empty
element (i=3), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 33
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 10 7 16 17 19
[0] [1] [2] [3] [4] [5]
Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=2) and insert into
10 7 the empty node
3. Store the deleted element in the last empty
element (i=2), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 34
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

15 7 10 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=2) and insert into
10 the empty node
3. Store the deleted element in the last empty
element (i=2), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 35
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=2) and insert into
10 the empty node
3. Store the deleted element in the last empty
element (i=2), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 36
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=2) and insert into
10 the empty node
3. Store the deleted element in the last empty
element (i=2), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 37
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 7 15 16 17 19
[0] [1] [2] [3] [4] [5]

10 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=2) and insert into
7 the empty node
3. Store the deleted element in the last empty
element (i=2), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 38
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 7 15 16 17 19
[0] [1] [2] [3] [4] [5]

10 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=1) and insert into
7 the empty node
3. Store the deleted element in the last empty
element (i=1), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 39
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 7 15 16 17 19
[0] [1] [2] [3] [4] [5]
Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=1) and insert into
7 the empty node
3. Store the deleted element in the last empty
element (i=1), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 40
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

10 7 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=1) and insert into
the empty node
3. Store the deleted element in the last empty
element (i=1), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 41
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=1) and insert into
the empty node
3. Store the deleted element in the last empty
element (i=1), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 42
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

NEXT: HEAP SORT

 2. Sort the heap  to make it in ascending order

7 10 15 16 17 19
[0] [1] [2] [3] [4] [5]

7 Steps:
SORTED
1. Delete the max element (parent, i=0) in BT
2. Move the last element (i=1) and insert into
the empty node
3. Store the deleted element in the last empty
element (i=1), not in heap
4. Select the inserted element (i=0), find its
child (i=1 and i=2)
5. Compare the child, select the greater child
6. If the child greater than parent, swap it
7. Repeat the step 1 until 5 for the next parent
until reach the last element 43
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

HEAP SORT SAMPLE CODE

#include <stdio.h>

void main()
{
int heap[10], no, i, j, c, root, temp, k;

printf("\n Enter no of elements :");

scanf("%d", &no);
printf("\n Enter the element : ");
for (i = 0; i < no; i++)
scanf("%d", &heap[i]);
for (i = 1; i < no; i++)
{
c = i;
for (c = i; c > 0; c=root)
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp; 44
}
}
}
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

for (j = no - 1; j >= 0; j--)

{
temp = heap[0];
heap[0] = heap[j]; /* swap max element with rightmost leaf element
*/
heap[j] = temp;

root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c < j) /* again rearrange to max heap
array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
45
}
 Dr Mohd Azwan & Dr Suryanti, Faculty of Computing, UMP, 2020

Sorts in O(NlogN) time by performing

N times deleteMax operations.
- Each deleteMax operation takes log N
running time.
- N times performing deleteMax  NlogN
running time

Used for general purpose sorting,

guarantees O(N logN)

COMPLEXITY
46