1 of 21

Naive Heap Sort

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put largest item at the end of the unused part of the output array.

32

15

2

17

19

26

41

17

Input:

2 of 21

Naive Heap Sort: Phase 1: Heap Creation

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.

32

15

2

17

19

26

41

17

Input:

41

19

32

17

2

26

15

17

Heap:

41

19

32

17

2

26

15

17

0

(Recall our heap implementation left position 0 unused)

Size: 9

3 of 21

Naive Heap Sort: Phase 1: Heap Creation

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Test your understanding: What is the runtime to complete this step?

32

15

2

17

19

26

41

17

Input:

41

19

32

17

2

26

15

17

41

19

32

17

2

26

15

17

Heap:

0

(Recall our heap implementation left position 0 unused)

Size: 9

4 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put largest item at the end of the unused part of the output array.

41

19

32

17

2

26

15

17

Output:

0

41

19

32

17

2

26

15

17

Heap:

0

Size: 9

5 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

32

19

26

17

2

17

15

Output:

0

41

32

19

26

17

2

17

15

0

Heap:

0

Size: 8

sorted

6 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

32

19

26

17

2

17

15

Output:

0

41

32

19

26

17

2

17

15

0

Heap:

0

Size: 8

sorted

7 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

26

19

17

2

15

Output:

0

32

41

26

19

17

2

15

0

Heap:

0

Size: 7

sorted

8 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

26

19

17

2

15

Output:

0

32

41

26

19

17

2

15

0

Heap:

0

Size: 7

sorted

9 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

19

17

15

2

Output:

0

26

32

41

19

17

15

2

0

Heap:

0

Size: 6

sorted

10 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

19

17

15

2

Output:

0

26

32

41

19

17

15

2

0

Heap:

0

Size: 6

sorted

11 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

2

15

Output:

0

19

26

32

41

17

2

15

0

Heap:

0

Size: 5

sorted

12 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

2

15

Output:

0

19

26

32

41

17

2

15

0

Heap:

0

Size: 5

sorted

13 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

15

17

2

Output:

0

17

19

26

32

41

17

15

17

2

0

Heap:

0

Size: 4

sorted

14 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

15

17

2

Output:

0

17

19

26

32

41

17

15

2

0

Heap:

0

Size: 4

sorted

15 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

15

2

Output:

0

17

19

26

32

41

17

15

2

0

Heap:

0

Size: 3

sorted

16 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

17

15

2

Output:

0

17

19

26

32

41

17

15

2

0

Heap:

0

Size: 3

sorted

17 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

15

2

Output:

0

17

19

26

32

41

15

2

Heap:

0

Size: 2

sorted

18 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

15

2

Output:

0

17

19

26

32

41

15

2

Heap:

0

Size: 2

sorted

19 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

2

Output:

0

15

17

19

26

32

41

2

0

Heap:

0

Size: 1

sorted

20 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

2

Output:

0

15

17

19

26

32

41

2

0

Heap:

0

Size: 1

sorted

21 of 21

Naive Heap Sort: Phase 2: Heap Deletion

Heap sorting N items:

Insert all items into a max heap, and discard input array. Create output array.
Repeat N times:

Delete largest item from the max heap.
Put deleted item at the end of the unused part of the output array.

2

Output:

2

15

17

19

26

32

41

0

Heap:

0

Size: 0

sorted