Heap Properties

Heaps (or Priority Queues) are specialized tree-based data structures that enable efficient retrieval of the minimum (min-heap) or maximum (max-heap) element.

1. Heap Overview

• Priority Queue: A dynamic data structure where elements are ordered by priority (not insertion time).
• Min-Heap: The root node holds the smallest value.
• Max-Heap: The root node holds the largest value.
• Key Operations:
  • Insertion (push).
  • Removal of the root (pop).

2. Structure Property

A heap is a complete binary tree:

• All levels (except the last) are fully filled.
• Last level is filled left-to-right with no gaps.
• Efficient Array Representation:
  • Avoids pointers by leveraging parent-child index relationships.

Example:

         14
       /    \
     19      16
    /  \    /  \
  21   26  19   68
 / \
65 30

Array Representation:

[ -, 14, 19, 16, 21, 26, 19, 68, 65, 30 ] (Index 0 is unused).

3. Order Property