Construct min heap from the given sequence

two methods on how to construct a min-heap using a sequence od data.

1. Data Structures and algorithms Min-heap construction SADIA ZAR Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 1

2. Min-heap – DATA STRUCTURE Construct a min-heap from the following sequence: 15, 3, 6, 18 ,5 ,9 ,11 In this lecture I’ve discussed two methods to construct a min-heap. Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 2

3. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 In the first method, at first we will construct a complete binary tree first and then we will check the condition i.e A[Parent[i]] < = A[i] for every node in the tree. Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 3

4. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 4

5. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 5

6. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 6

7. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 6 18 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 7

8. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 6 18 5 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 8

9. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 18 5 6 9 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 9

10. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 15 3 18 5 6 9 11 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 10

11. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes 15 3 18 5 6 9 11 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 11

12. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes i = 3 Parent[i] = Parent[3] = 1 So the condition is A[1] <= A[3] i.e, 3 <= 18 so no need to swap 15 3 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 12

13. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes i = 4 Parent[i] = Parent[4] = 1 So the condition is A[1] <= A[4] i.e, 3 <= 5 so no need to swap 15 3 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 13

14. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes i = 5 Parent[i] = Parent[5] = 2 So the condition is A[2] <= A[5] i.e, 6 <= 9 so no need to swap 15 3 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 14

15. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes i = 6 Parent[i] = Parent[6] = 2 So the condition is A[2] <= A[6] i.e, 6 <= 11 so no need to swap 15 3 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 15

16. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes i = 1 Parent[i] = Parent[1] = 0 So the condition is A[0] <= A[1] i.e, 15 <= 3 (false) so we have to swap 15 3 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 16

17. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes After swapping check other nodes as well i = 2 Parent[i] = Parent[2] = 0 So the condition is A[0] <= A[2] i.e, 3 <= 6 so no need to swap 3 15 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 17

18. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes Again check all the nodes now the problem Lies in node 1 and node 4 i = 4 Parent[i] = Parent[4] = 1 So the condition is A[1] <= A[4] i.e, 15 <= 5 (false) so we have to swap 3 15 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 18

19. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes Now again check i = 4 Parent[i] = Parent[4] = 1 So the condition is A[1] <= A[4] i.e, 5 <= 15 so no need to swap 3 5 18 15 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 19

20. Min-heap – DATA STRUCTURE First Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes As you can see that the min-heap is ready 3 15 18 5 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 20

21. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 In the second method, as we construct a complete binary tree, we will check the condition i.e A[Parent[i]] < = A[i] for every node that is inserted in the tree. Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 21

22. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 15 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 22

23. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 1 Parent[i] = Parent[1] = 0 Check the condition A[0]<=A[1] 15<=3 (false) so, we need to swap these two values 15 3 1 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 23

24. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 1 Parent[i] = Parent[1] = 0 Check the condition A[0]<=A[1] 3<=15 (true) so, continue 3 15 1 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 24

25. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 2 Parent[i] = Parent[2] = 0 Check the condition A[0]<=A[2] i.e, 3<=15 so no need to swap 3 15 1 6 2 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 25

26. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 3 Parent[i] = Parent[3] = 1 Check the condition A[1]<=A[3] i.e, 15<=18 so no need to swap 3 15 1 6 2 18 3 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 26

27. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 4 Parent[i] = Parent[4] = 1 Check the condition A[1]<=A[4] i.e, 15<=5 (false) so we have to swap 3 15 1 6 2 18 3 5 4 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 27

28. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 No the min-heap is okay 3 5 1 6 2 18 3 15 4 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 28

29. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 5 Parent[i] = Parent[5] = 2 Check the condition A[2]<=A[5] i.e, 6<=9 so no need to swap 3 5 1 6 2 18 3 15 4 9 5 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 29

30. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 i = 6 Parent[i] = Parent[6] = 2 Check the condition A[2]<=A[6] i.e, 6<=11 so no need to swap 3 5 1 6 2 18 3 15 4 9 5 11 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 30

31. Min-heap – DATA STRUCTURE SECOND Method - 15, 3, 6, 18 ,5 ,9 ,11 Now Let’s check the condition for every node Starting from leaf nodes As you can see that the min-heap is ready 3 5 18 15 6 9 11 1 2 3 4 5 6 Government Viqar-un-Nisa Post Graduate College (W), Rawalpindi. 31