Heap Properties

A heap is a specialized tree-based data structure that satisfies the heap property. It's the foundation for priority queues and efficient sorting. Understanding heap structure is key to understanding how priority queues achieve O(log n) operations.

What is a Heap?

A heap is a complete binary tree where every node satisfies the heap property:

• Max-Heap: Every parent is greater than or equal to its children
• Min-Heap: Every parent is less than or equal to its children

Max-Heap:                    Min-Heap:
       90                          10
      /  \                        /  \
    70    80                    20    30
   /  \   /                    /  \   /
  40  50 60                   40  50 60

Parent >= Children          Parent <= Children

Complete Binary Tree

A heap is always a complete binary tree:

• All levels are fully filled except possibly the last
• The last level is filled from left to right

Complete:                Not Complete:

       1                        1
      / \                      / \
     2   3                    2   3
    / \  /                   /     \
   4  5 6                   4       5
                                   (gap)

This property allows us to store the heap in an array without wasting space.

Array Representation

Because a heap is complete, we can use an array:

Max-Heap Tree:            Array: [90, 70, 80, 40, 50, 60]
       90                 Index:   0   1   2   3   4   5
      /  \
    70    80
   /  \   /
  40  50 60

Navigation formulas (0-indexed):

• Parent of node at index i: (i - 1) // 2
• Left child of node at index i: 2 * i + 1
• Right child of node at index i: 2 * i + 2

def parent(i):
    return (i - 1) // 2

def left_child(i):
    return 2 * i + 1

def right_child(i):
    return 2 * i + 2

Array: [90, 70, 80, 40, 50, 60]
Index:   0   1   2   3   4   5

Node 90 (index 0):
  - Left child: index 1 (70)
  - Right child: index 2 (80)

Node 70 (index 1):
  - Parent: index 0 (90)
  - Left child: index 3 (40)
  - Right child: index 4 (50)

Node 80 (index 2):
  - Parent: index 0 (90)
  - Left child: index 5 (60)
  - Right child: index 6 (doesn't exist)

Min-Heap vs Max-Heap

| Property | Min-Heap | Max-Heap | |----------|----------|----------| | Root | Minimum element | Maximum element | | Parent vs children | Parent ≤ children | Parent ≥ children | | Get min/max | O(1) | O(1) | | Extract min/max | O(log n) | O(log n) | | Insert | O(log n) | O(log n) |

Heap Property Verification

Check if an array represents a valid max-heap:

def is_max_heap(arr):
    n = len(arr)

    for i in range(n):
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[i] < arr[left]:
            return False
        if right < n and arr[i] < arr[right]:
            return False

    return True

print(is_max_heap([90, 70, 80, 40, 50, 60]))  # True
print(is_max_heap([90, 80, 70, 85, 50, 60]))  # False (80 < 85)

Height of a Heap

Because heaps are complete binary trees:

• A heap with n nodes has height ⌊log₂(n)⌋
• Operations traverse from root to leaf: O(log n)

n = 7 nodes:              n = 15 nodes:

       1    height = 2          1       height = 3
      / \                      / \
     2   3                    2   3
    /\ /\                   / \ / \
   4 5 6 7                 4  5 6  7
                          /\ /\ /\ /\
                         8 9...   ...15

height = floor(log₂(7)) = 2    height = floor(log₂(15)) = 3

Priority Queue Interface

Heaps implement priority queues efficiently:

class MinHeap:
    def __init__(self):
        self.heap = []

    def peek(self):
        """Return minimum element without removing."""
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]

    def push(self, val):
        """Add element to heap."""
        # Will implement with sift_up

    def pop(self):
        """Remove and return minimum element."""
        # Will implement with sift_down

    def __len__(self):
        return len(self.heap)

    def __bool__(self):
        return len(self.heap) > 0

Why Not Use a Sorted Array?

| Operation | Sorted Array | Heap | |-----------|--------------|------| | Find min/max | O(1) | O(1) | | Insert | O(n) | O(log n) | | Delete min/max | O(1) or O(n)* | O(log n) |

*O(1) if you can leave a gap, O(n) to shift elements

Heaps provide a better balance for dynamic priority queues.

Common Applications

1. Priority Queues: Task scheduling, event-driven simulation
2. Heap Sort: O(n log n) sorting algorithm
3. Graph Algorithms: Dijkstra's, Prim's algorithms
4. Top-K Problems: Find k largest/smallest elements
5. Median Maintenance: Using two heaps

Language Support

Most languages provide heap/priority queue implementations:

| Language | Min-Heap | Max-Heap | |----------|----------|----------| | Python | heapq module | Negate values or use heapq._heapify_max | | Java | PriorityQueue | PriorityQueue with custom comparator | | C++ | priority_queue (max by default) | Default behavior | | Go | container/heap | Implement heap.Interface | | Rust | BinaryHeap (max) | Use Reverse wrapper for min |

import heapq

# Python's heapq is a min-heap
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)

print(heapq.heappop(min_heap))  # 3
print(heapq.heappop(min_heap))  # 5

# For max-heap, negate values
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)

print(-heapq.heappop(max_heap))  # 7

Key Takeaways

1. Heaps are complete binary trees with the heap property
2. Min-heap: parent ≤ children; Max-heap: parent ≥ children
3. Array representation using index formulas for parent/children
4. O(1) access to min/max, O(log n) insert and extract
5. Foundation for priority queues and heap sort
6. Height is always O(log n) due to completeness

Understanding heap structure is essential before learning heap operations (push, pop, heapify). The array representation and navigation formulas are key to implementing efficient heap algorithms.