Binary Heaps

A Heap is a specialized tree-based data structure that satisfies the **Heap Property**: In a Max-Heap, the parent is always greater than or equal to its children. In a Min-Heap, the parent is always smaller. This allows you to find the 'Top' or 'Bottom' element in O(1) time.

1. Implementing via Array

Heaps are almost always implemented using a simple **Array** instead of pointers.

• Parent Index: (i - 1) / 2
• Left Child: (2 * i) + 1
• Right Child: (2 * i) + 2

2. Priority Queues

A Priority Queue is a data structure where elements with higher priority are served first. It is powered by a Heap. Every time you remove the top element, the heap performs a Heapify-Down (O(Log N)) to find the next highest priority item.

4. Interview Mastery

Q: "Why is a Binary Heap better than a Sorted Array for a Priority Queue?"

Architect Answer: "With a sorted array, inserting a new priority item takes **O(N)** because you have to shift all existing elements. With a Binary Heap, inserting takes only **O(Log N)**. Since a Priority Queue is constantly being updated with new tasks, the Heap is significantly more efficient for high-frequency writes."