Slide 8, Revision and Final Exam Info

Red-Black tree is NOT involved in Final Exam!!!

Heap

Hepify

From the last non-leaf node to the root, for each node:

1. Compare the node with its children
2. Swap it with the largest child if the child is larger
3. Repeat this process (heapify down) until the subtree is a valid max heap

Heap Sort (showing intermediate heaps)

Swap the largest unsorted element and the last unsorted element, mark the largest as sorted.

Given

[40, 30, 15, 10, 20]
       40
     /    \\
   30      15
  /  \\
10   20

1. Swap 40 and 20

   → [20, 30, 15, 10, 40] # sorted: 40
   

2. Swap 30 and 10

   → [20, 10, 15, 30, 40] # sorted: 30, 40
   

3. Swap 20 and 15

   → [15, 10, 20, 30, 40] # sorted: 20, 30, 40
   

4. Swap 15 and 10

   → [10, 15, 20, 30, 40] # sorted: 15, 20, 30, 40
   

5. All sorted

Inorder/Preorder/Postorder

Just write on your 2-sided A4 paper