• Heap-up: move element from lower to the top of the tree
• ใช้ BFT 09 Tree and Binary Tree
• เวลา remove เอา the last one (อิงจาก BFT) ไปเป็น Root อันใหม่— แล้วค่อย Compare root กับลูก ๆ ว่าอันไหน Tallest ก็ไปเป็น The new root

The structure that guarantee that we’ll have the largest value at the root

Heap

• A heap is a binary tree with the two properties
  • It must be complete or nearly complete
  • The key value of each node is greater than or equal to the key value in each of its descendents.
• This type of Heaps are called max-heap.
• ==The root is guaranteed to hold the largest node==
• ไม่มีเหมือน 10 Binary Search Tree ที่มี Control ว่า Left Child, Right Child ต้องน้อยกว่า มากกว่ายังไง

Max heap vs Min heap

• A min heap is a complete or nearly complete binary tree in which the value of each node is smaller than or equal to the value in each of its descendants.
• In our class, only Max heap is studied.

Heap Structure

BTs which are not heaps

Maintenance Operations

• Heaps are restricted BTs where we can insert a node to it and delete a node from it
• Insertion requires Reheap Up
• Deletion requires Reheap Down (take the smallest element (at the top) to the correct position)

Inserting data to a heap

1. Put the new data next to the last one, If the last one is the last position in the level, put the new data on the new level
   

2. Perform reheap up to maintain the heap

   • The reheap up operation repairs the structure by swapping with its parent level by level until it reaches to the correct position
   • Reheap up คือ Swap จนกว่ามันจะอยู่ในตำแหน่งที่ถูกต้อง ดูที่ Value ของมัน

   

Deleting the element from a heap

1. Delete the last element and replace it in the position of the element you desire to delete

   • ก็คือถ้าสมมติว่าอยากจะลบ Root ก็ลบออกไปเลย แล้ว Replace ด้วยตัวสุดท้าย (จะ Replace ได้แต่ต้องลบตัวสุดท้ายไปด้วยนะ)

2. To fix the heap structure, perform reheap down. To reheap down, the root value is swapped with the largest child, and this process is done repeatedly until it is in a position where the heap-ordering property is satisfied.

   • หลังจากนั้นก็ Reheap down ให้มันอยู่ตำแหน่งที่ถูกต้อง

   

Heap Array

• Heaps are preferably implemented in an array rather than a linked list.
• When we implement a heap in an array, we are able to calculate the location of the left and right sub-trees.
• This implementation is possible because of its complete or nearly complete properties.

Heap Implementation

• The index of the array is given according to the order of nodes visited in breadth first traversal (BFT) fashion

Index Relationships

• Parent of H[i] is H[floor((i-1)/2)]
• Left Child of H[i] is H[2*i+1]
• Right Child of H[i] is H[2*i+2] หรือว่าจะมองเป็น Left + 1 ก็ได้

Operations in Heap Array

Insertion

• ก่อนอื่นให้ Add Data เข้าไปหลังสุดของ Array ก่อน แล้วเขียน Parent ว่าอยู่ตำแหน่งที่เท่าไหร่ ใช้สูตร H[floor((i-1)/2)] แล้วก็หาไปเรื่อย ๆ จนถึงตัวหน้าสุด พอ Add ทีก็เปรียบเทียบเรื่อย ๆ!

Deletion

• วิธีง่าย ๆ เลย คือเขียน Parent ของทุกตัวไว้ด้านบนเลย จะได้ Compare ง่าย ๆ

Performance of Heap’s operations

• As a heap is guarantee to be balanced, the worst case performance of insertion and deletion in Heap is $O(\log n)$
  • Recall: The height of a complete or nearly complete Binary Tree is $\lceil(\log_2(n+1))\rceil$ 09 Tree and Binary Tree

Insertion

1. Add a new node at the last location: $O(1)$
2. Perform reheap up: $O(\log n)$

• Overall: $O(\log n)$

Root Deletion

1. Replace the root with the last data: $O(1)$
2. Remove the last data: $O(1)$
3. Perform reheap down: $O(\log n)$

• Overall: $O(\log n)$

findMax

• $O(1)$ มาได้ไง หาคำตอบหน่อย

Heap Sort Application

• Heap sort, which is based on max-heap, can be used to sort numbers from largest to smallest.
• This is done by repeatedly removing the largest element from the heap and performing reheapUp.