Heap vs Sorted Array — When to Use Which

The question

You need to repeatedly get the smallest (or largest) element. Do you use a heap or keep a sorted array?

Sorted array

• Get min/max: O(1) — it's at index 0 or n-1
• Insert: O(n) — must shift elements
• Best when: mostly reads, rare inserts

Binary heap

• Get min/max: O(1)
• Insert: O(log n)
• Extract: O(log n)
• Best when: many inserts and extracts — priority queues, schedulers

import heapq

tasks = [(3, "low"), (1, "urgent"), (2, "medium")]
heapq.heapify(tasks)
priority, name = heapq.heappop(tasks)  # ("urgent", 1)

Rule of thumb