Hadron DaVinci

Heap Sort Tutorial

04 Jun 2021 - Hadron DaVinci

Example

Sort the given array with Heap Sort:

A = [5, 2, 4, 6, 1, 3]
heap_sort(A)
assert(A) == [1, 2, 3, 4, 5, 6]

Method 1

1. Setup Binary Tree using input array
   • assume breadth-first order

2. Create Max Heap

3. While tree has nodes
   • append root node into array
     • use a deque to append left
   • swap root node and last node values
   • delete last node
   • reheapify root node

Complexity

Time Complexity: N
Space Complexity: N

Method 2

Same as Method1 but done directly on input array.

Complexity

Time Complexity: NlogN
Space Complexity: 1

Code

method1.py