Hadron DaVinci

Create Max Heap Tutorial

27 May 2021 - Hadron DaVinci


Example

Create a Max Heap with the following array. [-3, 11, 52, 4, 23, 70, 65, 100]

breadth_first_order = [-3, 11, 52, 4, 23, 70, 65, 100]
h = BinaryTree(breadth_first_order)

After Max Heaped
       ____100___
      /          \
    _23          _70
   /   \        /   \
  11    -3     52    65
 /
4


Method 1

  1. Setup Binary Tree with array

  2. Heapifies all descendants of root recursively

    • if child participates in swap, then heapify child

Complexity

Time Complexity: N
Space Complexity: N


Method 2

  1. Setup Binary Tree with a preorder

  2. Traverse tree in reverse-level order and heapify node

    • if child participates in swap, then heapify child

Complexity

Time Complexity: N
Space Complexity: N


Method 3

same as Method 2 but input is an array in breadth-first order


Code

method1.py
method2.py
method3.py