1 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array.
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

32

15

2

17

19

26

41

17

17

Input:

2 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Note: This is not a heap yet! That’s why we’re heapifying.

3 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 17 has no effect.

4 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

root

of a

heap

5 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 17 has no effect.

root

of a

heap

6 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

root

of a

heap

root

of a

heap

7 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 41 has no effect.

root

of a

heap

root

of a

heap

8 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

root

of a

heap

root

of a

heap

root

of a

heap

9 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 26 has no effect.

root

of a

heap

root

of a

heap

root

of a

heap

10 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

11 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 19 has no effect.

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

12 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

32

15

2

17

19

26

41

17

17

Input:

root

of a

heap

13 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 17 has no effect.

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

14 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

The blue coloring is to make it clear that the three 17s are all part of the same heap. I’ve also grayed out the “root of a heap” statement about the last two 17s since this is redundant information (all subheap nodes are also roots of that subheap).

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

15 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

2

17

19

26

41

17

17

Input:

32

15

2

17

19

26

41

17

17

Sinking 2 does something!

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

16 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

41

17

19

26

2

17

17

Input:

32

15

41

17

19

26

2

17

17

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

17 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

15

41

17

19

26

2

17

17

Input:

32

15

41

17

19

26

2

17

17

Sinking 15 does something!

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

18 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

19

41

17

15

26

2

17

17

Input:

32

19

41

17

15

26

2

17

17

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

19 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

32

19

41

17

15

26

2

17

17

Input:

32

19

41

17

15

26

2

17

17

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

Sinking 32 does something!

20 of 29

In-place Heap Sort: Phase 1: Heapification

Heap sorting N items:

  • Bottom-up heapify input array:
    • Sink nodes in reverse level order: sink(k)
    • After sinking, guaranteed that tree rooted at position k is a heap.

​

Punchline: Since tree rooted at position 0 is the root of a heap, then entire array is a heap.

41

19

32

17

15

26

2

17

17

Input:

41

19

32

17

15

26

2

17

17

(No room to leave an unused, spot, so we will actually use position zero for this algorithm!)

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

root

of a

heap

21 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

41

19

32

17

15

26

2

17

17

Input:

41

19

32

17

15

26

2

17

17

Size: 9

22 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

41

19

32

17

15

26

2

17

17

Input:

41

19

32

17

15

26

2

17

17

Size: 9

23 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

32

19

26

17

15

17

2

17

41

Input:

32

19

26

17

15

17

2

17

Size: 8

sorted

24 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

32

19

26

17

15

17

2

17

41

Input:

32

19

26

17

15

17

2

17

Size: 8

sorted

25 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

26

19

17

17

15

17

2

32

41

Input:

26

19

17

17

15

17

2

Size: 7

sorted

26 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

26

19

17

17

15

17

2

32

41

Input:

26

19

17

17

15

17

2

Size: 7

sorted

27 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

Give the array after this delete.

26

19

17

17

15

17

2

32

41

Input:

26

19

17

17

15

17

2

Size: 7

sorted

28 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

From here on out, the process is just the same, so verbose steps are omitted...

19

17

17

2

15

17

26

32

41

Input:

19

17

17

2

15

17

Size: 6

sorted

29 of 29

In-place Heap Sort

Heap sorting N items:

  • Bottom-up heapify input array (done!).
  • Repeat N times:
    • Delete largest item from the max heap, swapping root with last item in the heap.

2

15

15

17

17

19

26

32

41

Input:

Size: 0

sorted