A heap is a special tree structure, typically implemented based on a complete binary tree, and satisfies the properties of a max-heap or min-heap. In simple terms, a heap is a “special complete binary tree” where the value of each parent node is either greater than or equal to its child nodes (max-heap) or less than or equal to its child nodes (min-heap). This structure allows heaps to efficiently retrieve the maximum or minimum value, making them widely used in algorithms.

Heap Storage Method¶

Heaps are usually stored in arrays because the structure of a complete binary tree can be directly mapped to parent-child relationships using array indices. Suppose the array index is i (starting from 0):
- The index of the left child is 2*i + 1
- The index of the right child is 2*i + 2
- The index of the parent is (i - 1) // 2 (integer division)

For example, the element at index 0 is the root node, with left child at index 1 and right child at index 2. The parent of index 1 is index 0, with left child at index 3 and right child at index 4, and so on.

Max-Heap vs Min-Heap¶

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

Examples:
- Max-heap array: [9, 5, 7, 3, 6, 2, 4] (root 9 is the maximum)
- Min-heap array: [3, 6, 5, 9, 7, 2, 4] (root 3 is the minimum)

Basic Heap Operations¶

The core operations of a heap include insertion, deletion, heap construction, and retrieving the top element, all of which rely on adjustment mechanisms (percolate up or down).

1. Insertion (Percolate Up)¶

Purpose: Add an element to the heap while maintaining heap properties.
Steps:
1. Append the new element to the end of the array (the last empty position in the complete binary tree).
2. Compare the new element with its parent starting from its position:
- For a max-heap: If the new element is greater than the parent, swap them.
- For a min-heap: If the new element is less than the parent, swap them.
3. Repeat step 2 until the parent-child property is satisfied or the root is reached.

Example (Insert 10 into a max-heap):
Original max-heap array: [9, 5, 7, 3, 6, 2, 4] (length 7)
- Insert 10 at the end: [9, 5, 7, 3, 6, 2, 4, 10]
- New element at index 7, parent index (7-1)//2 = 3 (value 3). Since 10 > 3, swap → [9, 5, 7, 10, 6, 2, 4, 3]
- New element at index 3, parent index (3-1)//2 = 1 (value 5). Since 10 > 5, swap → [9, 10, 7, 5, 6, 2, 4, 3]
- New element at index 1, parent index (1-1)//2 = 0 (value 9). Since 10 > 9, swap → [10, 9, 7, 5, 6, 2, 4, 3]
- Stop (root reached). Final array: [10, 9, 7, 5, 6, 2, 4, 3]

2. Deletion (Percolate Down)¶

Purpose: Remove the top element (max for max-heap, min for min-heap) while maintaining heap properties.
Steps:
1. Swap the root (index 0) with the last element, then remove the last element.
2. Starting from the new root, compare with its children:
- For a max-heap: Compare left and right children, take the maximum. If the root is less than this maximum, swap.
- For a min-heap: Compare left and right children, take the minimum. If the root is greater than this minimum, swap.
3. Repeat step 2 until the parent-child property is satisfied or a leaf node is reached.

Example (Delete root 10 from a max-heap):
Original max-heap array: [10, 9, 7, 5, 6, 2, 4] (length 7)
- Swap root (10) with last element (4): [4, 9, 7, 5, 6, 2, 10], then remove 10 → [4, 9, 7, 5, 6, 2]
- New root (4) has children at indices 1 (9) and 2 (7). Max child is 9. Since 4 < 9, swap → [9, 4, 7, 5, 6, 2]
- New root (4) at index 1 has children at indices 3 (5) and 4 (6). Max child is 6. Since 4 < 6, swap → [9, 6, 7, 5, 4, 2]
- Stop (no children for 4 at index 4). Final array: [9, 6, 7, 5, 4, 2]

3. Heap Construction¶

Purpose: Convert an unordered array into a heap.
Steps:
1. Find the last non-leaf node (index n//2 - 1, where n is the array length).
2. From this node, perform percolate down on each node (moving upward by decreasing index) until the root.

Example (Build a max-heap from [3, 1, 2, 6, 4, 5]):
- Array length n=6, last non-leaf index 6//2 - 1 = 2 (value 2)
- Process index 2 (value 2): Children at 3 (6) and 4 (4). Max is 6. Swap → [3, 1, 6, 2, 4, 5]
- Process index 1 (value 1): Children at 3 (2) and 4 (4). Max is 4. Swap → [3, 4, 6, 2, 1, 5]
- Process index 0 (value 3): Children at 1 (4) and 2 (6). Max is 6. Swap → [6, 4, 3, 2, 1, 5]
- Stop. Final max-heap array: [6, 4, 3, 2, 1, 5]

4. Retrieve Top Element¶

Directly return the element at index 0 (root node), which is the maximum (max-heap) or minimum (min-heap).

Heap Applications¶

Heaps are efficient for:
- Priority Queues: E.g., task scheduling (priority-based execution) and frequent element statistics.
- Heap Sort: Time complexity O(n log n), more efficient than bubble sort or insertion sort.
- Top K Problems: Quickly find the K largest/smallest elements in an array.

Summary¶

A heap is a special structure based on complete binary trees, stored in arrays with insertion/deletion via percolate operations. It efficiently supports insertion, deletion, and extremum retrieval. Mastering heap concepts is crucial for understanding algorithms like sorting and priority queues. Beginners can start with array-based heap simulations to practice adjustment processes.