Video Summary - 2.6.3 Heap - Heap Sort - Heapify

Main ideas / lessons conveyed

What a Heap is (and why it matters)
- A heap is a data structure based on a complete binary tree.
- Two common variants:
  - Max-Heap: every parent node value is greater than or equal to its descendants → the largest value is at the root.
  - Min-Heap: every parent node value is less than than or equal to its descendants → the smallest value is at the root.
- Heaps enable fast access to the “extreme” element (max or min) and are commonly used to implement Priority Queues.

Goal: store tree nodes in an array while preserving parent/child relationships.
Indexing assumption: the formulas are commonly shown using 1-based indexing (some programming languages use 0-based indexing, but the relationships are the same idea).
Relationships (with a node at index i):
- Left child: 2*i
- Right child: 2*i + 1
- Parent: floor(i/2)
How the mapping works:
- By filling nodes level-by-level, these formulas automatically align correctly.
Important case when nodes are missing:
- If a node is missing in the middle, you must leave a blank/gap in the array so that later nodes still map to the correct parent-child positions.

Full binary tree
- Completely filled at a given height (described as having the maximum nodes possible for that height).
- For height H, the maximum nodes are: 2^(H+1) - 1.
Complete binary tree
- When represented in an array, it should have no gaps between the first and last elements.
- Equivalent description:
  - All levels are full up to height H-1
  - The last level is filled from left to right
Key takeaway: a complete binary tree has minimal height for its number of nodes → height grows about log(n).

High-level approach:
1. Insert the new element in the last free position to keep the tree complete.
2. If the heap order property is violated, bubble the element up (swap with its parent) until fixed.
Procedure (as described):
- Add the element as a leaf at the end of the array (last available spot).
- While the new node’s value is greater than its parent:
  - swap it with the parent
  - continue upward toward the root
Direction note: leaf → root (upwards)
Complexity insight:
- Swaps depend on tree height.
- Since heap height is log(n), insertion takes O(log n) in the worst case.

Critical rule:
- You delete only the root (the maximum element in a Max-Heap).
Procedure (as described):
1. Remove the root (the element to delete).
2. Move the last element (last array element / last node in the complete tree) to the root position to preserve completeness.
3. Fix heap-order by pushing the element down:
  - compare the moved element with its children
  - swap with the larger child if the heap property is violated
  - continue down until it’s correctly placed
Direction note: root → leaf (downwards)
Complexity insight:
- Height is log(n) → deletion takes O(log n).

Core idea:
- Repeatedly deleting from a heap yields elements in sorted order.
- In a max-heap, deleting max repeatedly produces values in descending order; when placed into the array appropriately, the result is sorted.
Method described:
- After each deletion, the “deleted spot” becomes a free position.
- The next deleted root is written into the next free position.
- Continue until the heap is empty.
Key constraint maintained: the heap must remain a complete binary tree throughout.

Phase 1: Build the heap
- Given array elements:
  - Create a heap by inserting elements one by one.
- The video illustrates this as building a max-heap, though the concept generalizes.
Phase 2: Sort by repeated deletion
- While the heap is not empty:
  - Delete the root (current max in a max-heap)
  - place it into the next available free position outside/at the end of the heap region
Time complexity reasoning (as stated):
- Building heap via repeated insertion: O(n log n)
- Deleting all elements: n deletions, each O(log n) → O(n log n)
- Total: O(n log n) (described as about “2 * n log n”, still O(n log n))

Heapify meaning:
- A procedure to create a heap from an existing array without inserting elements one-by-one.
Key difference from insertion-based build:
- In insertion-based creation:
  - add at leaf and bubble up
- In heapify:
  - scan from right to left
  - for each node, enforce heap property by pushing downwards (like “bubble down”)
Procedure (conceptual steps):
- Starting from the last elements backward:
  - consider a node
  - assume its children are already heapified (due to traversal order)
  - if the node violates heap property with its children:
    - swap with the appropriate child (for max-heap: the larger child)
  - continue until the node settles correctly
Direction note: top/down toward leaves (similar to deletion)
Complexity claim:
- Heapify runs in O(n) time (presented as faster than insertion-based heap creation).

What a priority queue is:
- Like a queue, but removal is based on priority, not arrival order.
- On deletion, remove the element with the highest priority.
Priority definition examples (from the video):
- Case A: “smaller number = higher priority” → use a Min-Heap
- Case B: “larger number = higher priority” → use a Max-Heap
- The video’s example also mentions that the number itself can be treated as its priority.
Why heaps help vs. arrays:
- Arrays may require shifts, which can lead to O(n) insertion/deletion.
- With a heap:
  - insertion: O(log n)
  - deleting highest-priority element: O(log n)
Final takeaway:
- Priority queues can be efficiently implemented with heaps (min-heap or max-heap depending on priority rules).

Speaker: An unnamed instructor (video narrator/teacher)
External sources: None explicitly named (Udemy course links are mentioned, but no specific author/source is cited)