Heap Overview

A Heap is a specialized tree-based data structure that satisfies the Heap Property:

• Min-Heap: The value of each node is less than or equal to the values of its children. The root is the minimum.
• Max-Heap: The value of each node is greater than or equal to the values of its children. The root is the maximum.

It is commonly used to implement a Priority Queue.

Imagine you need to constantly retrieve the highest priority task from a dynamic list of tasks. You add new tasks (insert) and complete the highest priority one (extract max).

A standard Array or List is inefficient:

• Unsorted Array: Insert O(1), Get Max O(N).
• Sorted Array: Get Max O(1), Insert O(N).

We need a structure that balances these. A Heap does both in O(log N).

If you keep the array sorted, finding the max is fast (O(1)). But adding a new element requires shifting everyone else, costing O(N). If you have N insertions, that's O(N²). A Heap manages this dynamically in O(N log N) total for N insertions.

A Heap is usually a Complete Binary Tree.

• Insert: Add to the bottom-right, then "bubble up" (swap with parent) until heap property is restored.
• Extract: Remove root, move the last element to the root, then "bubble down" (swap with smaller child) until restored.

Because the tree height is log(N), these operations are fast.