Advanced Data Structures: Heaps and Hash Tables

Two tools for speed

Now that you've covered Greedy Algorithms and Their Applications, you're ready for two data structures that make many greedy and lookup-heavy solutions practical:

• Heaps: quickly access the smallest or largest item.
• Hash tables: quickly check, count, group, or retrieve items by key.

In a 30-day crash course, these are high-value because they appear everywhere in easy and medium problems. They also connect naturally to what you've already learned:

• From Algorithm Basics and Complexity Analysis: we care about reducing repeated scans.
• From Trees and Graphs: heaps are tree-shaped internally, even if Python hides the details.
• From Greedy Algorithms: heaps often help us repeatedly choose the best next option.

One brief foreshadow: heaps will show up again when you study shortest paths next lesson.

A heap is a priority machine

A heap is a data structure optimized for repeatedly answering:

What is the highest-priority item right now?

In Python, the built-in heapq module gives you a min-heap by default. That means the smallest item is always available at the front.

Conceptually:

        1
      /   \
     3     2
    / \   /
   8   5 4

The important rule is not full sorting. The heap only guarantees:

• the smallest value is at the root
• each parent is <= its children
• pushing and popping restore that rule

So a heap is perfect when you do not need a fully sorted list, only the next best item repeatedly.

Python heap basics

Python's heapq works on a normal list, but maintains heap order as you push and pop.

Main operations:

• heappush(heap, item) inserts an item in O(log n) time.
• heappop(heap) removes and returns the smallest item in O(log n) time.
• Looking at heap[0] gives the smallest item in O(1) time.

A common pattern is storing tuples like (priority, value). Python compares tuple elements from left to right, so the priority comes first.

```python
import heapq

tasks = []
heapq.heappush(tasks, (3, 'write notes'))
heapq.heappush(tasks, (1, 'fix urgent bug'))
heapq.heappush(tasks, (2, 'review code'))

print('Heap list:', tasks)

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'Priority {priority}: {task}')
```

You have a Python min-heap with n items. What is the usual time complexity of inserting one new item with heapq.heappush?

Hash tables trade order for access

A hash table stores values by using a key. In Python, you use hash tables constantly:

• dict maps keys to values.
• set stores unique keys.

The big idea:

key -> hash function -> bucket -> stored value

For coding interviews and daily problem practice, hash tables usually help with questions like:

• Have I seen this before?
• How many times has this appeared?
• Where did this value appear?
• Can I find the complement quickly?

Average-case lookup, insert, and delete are O(1), which is why hash tables often replace nested loops.

Turning a scan into memory

A classic beginner-to-medium pattern is:

As you scan, store what would help your future self.

For Two Sum, instead of checking every pair, keep a dictionary from number to index. For each number, ask whether its needed complement has already appeared.

This changes the approach from roughly O(n^2) pair checking to O(n) average time.

```python
def two_sum(nums, target):
    seen = {}  # number -> index

    for i, num in enumerate(nums):
        need = target - num

        if need in seen:
            return [seen[need], i]

        seen[num] = i

    return []

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
```

Fill in the blank:

Average-case lookup in a Python dict is usually ___ time.

Fill in the blank: _____________

True or false?

Python's heapq module creates a max-heap by default, so the largest item is popped first.

Heap or hash table?

Use the question shape to choose the tool.

Reach for a heap when...

• you repeatedly need the smallest/largest item
• you are maintaining a top k
• priorities change the processing order
• sorting everything would be more work than needed

Reach for a hash table when...

• you need fast membership checks
• you need counts or frequencies
• you need to map one thing to another
• a nested loop is only checking whether something exists

Common interview smell

If your first solution says, "for each item, scan all previous items," ask:

Could a dict, set, or heap remember the useful part for me?

Your 2-day revisit loop

Because this course is built for fast proficiency, don't just read this lesson once. Add these to your spaced review list.

Practice today

1. Two Sum using a dictionary.
2. Contains Duplicate using a set.
3. Top K Frequent Elements using a dictionary plus a heap.
4. Kth Largest Element using a heap.

Revisit in 2 days

Redo the same problems without looking at your first solution. Your goal is not memorizing code — it is recognizing the trigger:

• "I need fast lookup" → hash table.
• "I need repeated best item" → heap.

Next, you'll use these instincts alongside graph traversal ideas when the course moves into shortest path and connectivity.