Quiz 3 & Quiz 4 Study Guide

What a heap is

• A heap has a binary tree structure.
• A heap is not a binary search tree.
• It must be an almost complete tree.
• Nodes on the last level must be as far left as possible.
• The lecture uses an array-based min-heap.

Valid min-heap example

          10
        /    \
      20      40
     /  \    / \
   60   30  70  50

Each child is greater than its parent. The heap does not need to be fully sorted from left to right.

Heap vs. BST — quiz trap

Parent / child formulas — memorize these

Example from the heap layout

Index:  0   1   2   3   4   5
Value: 10  20  40  60  30  70

For the item 30, its index is i = 4.

If those child indexes are outside the current heap size, the node has no child there.

Fast mental check

For index i = 5:

Parent      = ⌊(5 - 1) / 2⌋ = 2
Left child  = 2(5) + 1       = 11
Right child = 2(5) + 2       = 12

How add works

1. Copy the new item into the left-most open position on the last level.
2. Compare the new item with its parent.
3. If the new item is smaller than its parent, swap them.
4. Continue moving upward until the heap property is restored.

Lecture-style pseudocode

Copy new item into left-most open item of last level

While item < parentOfItem
    swap(item, parentOfItem)
    item = parentOfItem

Example: add 5

       10
      /  \
    20    30

       10
      /  \
    20    30
   /
  5

Compare 5 with 20 → swap. Then compare 5 with 10 → swap.

        5
      /   \
    10     30
   /
  20

Big-O

The copy into the open slot is O(1), while heapify up is O(log n). The total is therefore O(log n).

What getMin does

In this lecture's heap implementation, getMin() returns and removes the root element.

1. Save the root value in a local variable.
2. Copy the right-most item on the last level into the root.
3. Decrease the heap size.
4. Compare the copied item with its children.
5. If necessary, swap it with its smaller child.
6. Continue downward until the heap property is restored.
7. Return the saved minimum.

Lecture-style pseudocode

Save root into minVal
Copy right-most item of last level into root

item = root
While item > leastChildOfItem
    swap(item, leastChildOfItem)
    item = leastChildOfItem

return minVal

leastChildOfItem means the smaller of the left and right children.

Why the smaller child?

In a min-heap, the replacement value must end up below a value that is no greater than it. Choosing the smaller child preserves the min-heap ordering as the item moves down.

Big-O

Overwriting the root is O(1). Heapify down is O(log n). Total: O(log n).

How delete works

1. Do a linear search through the array to find the item.
2. Copy the right-most item on the last level into the deleted item's position.
3. Check whether the replacement violates the heap property.
4. If the replacement is smaller than its parent, heapify up.
5. Otherwise, heapify down as necessary.

Big-O analysis

Definition

A priority queue is an ADT in which only the item with the highest priority can be accessed.

• It is similar to a queue, but priority determines which item comes out first.
• The highest-priority item is logically at the front.
• Items can be represented as <data, priority> pairs.
• The most important operations in the lecture are add and getMin.

Lecture example: lower value = higher priority

The slides explicitly make this assumption for the example.

Insert:

14, 32, 11

Logical priority order:

Front → 11 → 14 → 32 → Rear

Then enqueue 22:

Front → 11 → 14 → 22 → 32 → Rear

Logical view vs. actual heap storage

A heap-based priority queue may feel fully ordered from the user's perspective, but the actual heap is not fully sorted.

The table to memorize

*The slides state getMin = O(n) for the sorted array implementation when items are shifted after removal.

Why the costs differ

Know these cold

1. Array formulas: left = 2i + 1, right = 2i + 2, parent = ⌊(i - 1) / 2⌋.
2. Heapify direction: add → UP, getMin → DOWN, delete → UP or DOWN.
3. Heap Big-O: add O(log n), getMin O(log n), delete O(n).
4. Priority queue implementations: unsorted array O(1)/O(n), sorted array O(n)/O(n), heap O(log n)/O(log n).

Ultra-short version

MIN HEAP
root = minimum
parent <= children
almost complete binary tree
not a BST
not fully sorted

ARRAY INDEXES
left   = 2i + 1
right  = 2i + 2
parent = floor((i - 1) / 2)

HEAP OPERATIONS
add     → heapify UP   → O(log n)
getMin  → heapify DOWN → O(log n)
delete                 → O(n)

PRIORITY QUEUE
highest priority removed first
lecture example: lower number = higher priority

PQ IMPLEMENTATIONS
unsorted array: add O(1),     getMin O(n)
sorted array:   add O(n),     getMin O(n)
heap:           add O(log n), getMin O(log n)

Common quiz traps

1. A heap is not a BST.
2. A heap is not fully sorted; only the heap property is guaranteed.
3. getMin() in these slides removes the root.
4. Heap add inserts at the next open position first, then heapifies up.
5. Heapify down compares against the smaller child.
6. Arbitrary delete is O(n) because finding the item is linear.
7. The slide example assumes lower numbers have higher priority.

Try these without looking above

1. For a heap item at index 6, what are the indexes of its left child, right child, and parent?
2. In a min-heap, where is the smallest value located?
3. When a new value is inserted into a min-heap, where is it placed before any swaps occur?
4. Which operation normally uses heapify up: add or getMin?
5. During heapify down, which child should be used for the comparison in a min-heap?
6. What are the Big-O costs of add, getMin, and arbitrary delete in the lecture's array-based heap?
7. For an unsorted-array priority queue, what are the Big-O costs of add and getMin?
8. For a heap-based priority queue, what are the Big-O costs of add and getMin?
9. Starting with an empty min-heap, insert 10, 7, 19, 5, 16. What value ends up at the root?

Mini heap tracing

Start with this min-heap:

        4
      /   \
     9     7
    / \
   15 12

10. If 5 is added, where is it inserted initially?
11. After heapify up finishes, what is the root?
12. If getMin() is then called, what value is returned?
13. After the root is removed, which existing item is copied into the root before heapify down?

Answer Key

Main idea

The lecture's heapsort uses a min-heap.

• The heap holds the unsorted data.
• The array holds the sorted data.
• Repeatedly take the minimum element from the heap and place it into the next open location in the sorted region.
• This is similar to selection sort because both repeatedly select the minimum remaining item.

Heapsort pseudocode

Create an empty heap h

For all items in unsorted array
    h.add(current item)

sortedNextOpen = 0

While heap not empty
    min = h.getMin()
    Copy min to array[sortedNextOpen]
    Increment sortedNextOpen

Lecture example

Original list:

10, 7, 19, 5, 16

After all values are added to the min-heap:

        5
      /   \
     7     19
    / \
   10 16

Repeated getMin() calls produce:

5, 7, 10, 16, 19

Heapsort trace: build the min-heap (slides 7–12)

The lecture starts with [10, 7, 19, 5, 16] and inserts each value into an initially empty min-heap. Place it in the next open position of the complete tree, then heapify up if it is smaller than its parent.

Heap after all insertions:
       5
     /   \
    7     19
   / \
 10  16

Source: Heapsort, pp. 7–12.

Heapsort trace: remove the minimum five times (slides 13–28)

getMin() removes the root in the lecture's heap implementation: move the last heap element into the root, reduce the heap size, and heapify down by swapping with the smaller child as needed. Then write the removed minimum to array[sortedNextOpen] and advance that index.

First removal in slow motion:

Start:         [5, 7, 19, 10, 16]
Save min = 5; move last item to root:
               [16, 7, 19, 10]
Swap 16 with smaller child 7:
               [7, 16, 19, 10]
Swap 16 with smaller child 10:
               [7, 10, 19, 16]
Write array[0] = 5; sortedNextOpen = 1

The other four removals follow the same remove → repair heap → append to sorted region pattern. After the fifth call, the heap is empty and the array is sorted.

Source: Heapsort, pp. 13–28. Heap contents are shown in array/level order to make each slide's tree easier to trace.

Heapsort Big-O

Heapsort best, average and worst cases (slides 30–31)

Total for the method taught: O(1) + O(n log n) + O(n log n) = O(n log n).

Source: Heapsort, pp. 30–31.

Idea and algorithm

Selection sort is an elementary in-place sort. Divide the array into a growing sorted left part and a shrinking unsorted right part. To sort ascending, repeatedly find the minimum element in the unsorted part, swap it to the beginning of that part, and advance the boundary.

1. Initialize unsortedStart = 0.
2. Linearly search indexes unsortedStart through the end for the minimum.
3. Swap the minimum with data[unsortedStart] (a swap may be unnecessary).
4. Increment unsortedStart; repeat until everything is sorted.

Lecture walkthrough — 10, 7, 19, 5, 16

unsortedStart = 0
while unsortedStart < n:
    minIndex = unsortedStart
    for j = unsortedStart + 1 to n - 1:
        if data[j] < data[minIndex]:
            minIndex = j
    swap(data[unsortedStart], data[minIndex])
    unsortedStart++

Source: Selection Sort, pp. 4–22. The overview once says “highest,” but the pseudocode and complete ascending trace clearly select the minimum.

Complexity / exam traps

• It searches each unsorted suffix even when the input is already sorted: best is still O(n²).
• Extra space: O(1), in-place.
• Stability: ordinary swap-based selection sort is not stable, although a stable variation can be written (as noted in the Quicksort slides).

Source: Selection Sort, pp. 24–25; Quicksort, pp. 5–6.

Divide and conquer + pivot

Quicksort recursively partitions an array around a pivot. Values below the pivot go left; values above the pivot go right. When a partition pass ends, the pivot occupies its final sorted position. Recursively sort the two remaining parts, excluding that pivot; stop at subarrays containing zero or one item.

Lecture trace: first pivot = 50

Original:
50  40  10  70  60  20  90  80  30
^ pivot

After one partition:
30  40  10  20  |50|  70  90  80  60
   lower         pivot      higher

The pivot 50 is now in the correct place, but the elements within each partition are not yet fully sorted. Quicksort next sorts [30,40,10,20] and [70,90,80,60].

Source: Quicksort, pp. 7–8 and following partition slides.

First partition, step by step: i and j

Start with pivot 50 at index 0, i = 1 and j = 1. j scans the array; i is the next opening in the lower-than-pivot partition. The lower partition occupies indexes 1 through i - 1.

Initial:
50  40  10  70  60  20  90  80  30

After processing j = 5 (20 swaps with 70):
50  40  10  20  60  70  90  80  30

After processing j = 8 (30 swaps with 60):
50  40  10  20  30  70  90  80  60

Scan complete: i = 5
Swap pivot data[0] with data[i - 1] = data[4]:
30  40  10  20 |50| 70  90  80  60

Source: Quicksort, pp. 9–22.

Finish the lecture's Quicksort recursion

After placing pivot 50 at index 4, recursively sort the lower partition first, then the higher partition. Each recursive call picks the first element of its own subarray as the pivot.

Recursive call order (first-element pivot):
quicksort(0,8)    pivot 50
├─ quicksort(0,3) pivot 30
│  ├─ quicksort(0,1) pivot 20
│  │  ├─ quicksort(0,0) → base case
│  │  └─ quicksort(2,1) → empty
│  └─ quicksort(3,3) → base case
└─ quicksort(5,8) pivot 70
   ├─ quicksort(5,5) → base case
   └─ quicksort(7,8) pivot 80
      ├─ quicksort(7,6) → empty
      └─ quicksort(8,8) → base case

Final array:
10  20  30  40  50  60  70  80  90

Base case: if low >= high, there are zero or one elements in the region, so no partition is needed. After a partition, the pivot is already final; recursive calls exclude the pivot index.

Source: Quicksort, pp. 23–58; recursive call syntax summarized from the lecture's pseudocode on p. 59.

Partition pointers and pseudocode

quicksort(low, high):
    if low >= high: return
    p = partition(low, high)
    quicksort(low, p - 1)
    quicksort(p + 1, high)

partition(low, high):
    pivot = data[low]
    i = low + 1
    for j = low + 1 to high:
        if data[j] < pivot:
            swap(data[j], data[i])
            i++
    swap(data[low], data[i - 1])
    return i - 1

Big-O, recursion, and properties

• One partition of n values scans n items: O(n).
• Balanced recursion has about log n levels; terrible pivots yield about n levels.
• With a fixed first-element pivot, already sorted or reverse-sorted values may lead to the worst case.
• Quicksort rearranges the same array (in-place), although recursive calls need O(log n) average / balanced stack space and can reach O(n) worst case.
• Quicksort is not stable: duplicates need not retain their input order.

Source: Quicksort, pp. 5–6 and 60–64.

Randomized quicksort

Pick a pivot index uniformly at random, swap that value into the first slot, and perform the usual partition. A median pivot would balance the partitions ideally, but choosing the median is not required.

randIndex = randomly choose from low to high
swap(data[low], data[randIndex])
// continue with first-element-pivot partition

• Expected: O(n log n), including for initially sorted input.
• Absolute worst case: O(n²); unlucky pivots are still possible.

Source: Quicksort, pp. 65–69.

Map vs. hash table vs. hash set

• Map ADT: associates a unique key with a value, e.g. "Yankees" → 1.
• Operations: add/put(key,value), find/get(key), delete/remove(key).
• Hash table: an implementation of a map; alternatives include lists and binary search trees.
• Hash set: an unordered collection of unique values, not a collection of explicit key/value pairs.
• Hash function: transforms a key into an array index (the bucket) where its information is stored or searched for.

Bucket formula, collisions and a better hash

This is the lecture's simplified teaching example. With 10 buckets:

A collision occurs when different keys map to the same bucket. The slides explain that practical hashing usually transforms the key before using modulo, helping distribute keys more evenly.

hash(key):
    transformedKey = transform(key)
    return transformedKey % numBuckets

Searching costs — important comparison

SUHA, load factor and perfect hashing

Simple Uniform Hashing Assumption (SUHA): every key independently hashes to each bucket with equal probability. Under this assumption the expected bucket length is n/m, also called the load factor.

A perfect hash function has no collisions for a known set of keys. The slides note that it requires knowing possible keys beforehand; more keys than slots make collisions unavoidable.

Source: Hash Table Overview, pp. 3–6, 19–31.

How linked-list buckets handle collisions

Separate chaining uses an array of buckets, where each bucket is an unsorted linked list of nodes. Each node contains a key/value pair. Several different keys can occupy one bucket without replacing each other.

hash(key) = key % 10

bucket 0: [10] → [50] → [80]
bucket 1: [91] → [11] → [71]
bucket 2: [22] → [82] → [52]
bucket 3: [33]
bucket 4: [94] → [14]
bucket 5: empty
...
bucket 9: [49] → [19]

These diagrams show keys for simplicity, but the underlying nodes also hold values, e.g. <50, "Phone">.

Source: Separate Chaining, pp. 3–6.

add, find and delete

add(key, value):
    index = hash(key)
    insert (key, value) into table[index]

find(key):
    index = hash(key)
    search table[index] for matching key
    return its associated value if found

delete(key):
    index = hash(key)
    remove matching node from table[index]

Resize when projected load factor exceeds 0.75

Load factor = number of stored keys / number of buckets = n / m. The lecture checks before inserting: if the new item would make (n+1)/m > 0.75, resize.

1. Allocate a larger array (slides first illustrate roughly doubling the bucket count).
2. Rehash and reinsert every existing key/value pair since its bucket may change.
3. Insert the new entry.

Source: Separate Chaining, pp. 15–23.

Resize walkthrough from the slides: 16, 58, 19, 85

The lecture first uses exactly doubling as a simple illustration, starting with 2 buckets, hash(key) = key % bucketCount, and a threshold of 0.75.

2 buckets, before adding 58:
0: [16]
1: []

4 buckets, after adding 58 and 19:
0: [16]
1: []
2: [58]
3: [19]

8 buckets, after adding 85:
0: [16]   1: []    2: [58]   3: [19]
4: []     5: [85]  6: []     7: []

Source: Separate Chaining, pp. 15–23.

Why resizing by a constant amount breaks amortized O(1)

A resize takes O(n) because every stored key/value entry must be rehashed and inserted into the new array. The lecture's O(1) amortized insertion relies on increasing the array size by a multiplicative factor (doubling or close to doubling).

• Roughly doubling: after each resize, capacity for many future insertions is available. Cheap adds between resizes can account for the occasional expensive copy.
• Adding just 100 buckets each time: the number of adds between resizes stays roughly fixed while the number of elements copied at each resize keeps growing. The cheap adds cannot cover increasingly expensive copies at constant amortized cost.
• Tradeoff: expanding aggressively uses more unused buckets but makes resizing less frequent; expanding too slowly saves some capacity but increases copying work.

Source: Separate Chaining, pp. 17, 22–23 and 25–28 (especially the fixed-100-bucket counterexample on p. 26).

Performance — expected, amortized and worst case

Amortized O(1) add means occasional expensive resizing is spread across many inexpensive additions. Expected O(1) find and delete depend on good hashing (SUHA) and periodic resizing — they are not hard worst-case guarantees.

Source: Separate Chaining, pp. 17, 25–29.

Sorting Big-O comparison

Nine facts to memorize

1. Selection: repeated minimum + swap; Θ(n²) even on sorted input.
2. Quicksort: pivot is final after partition; recursively sort either side.
3. Randomized quicksort: expected O(n log n), absolute worst O(n²).
4. Map: key/value pairs; set: unique values.
5. Hash function: key → bucket; two keys at one bucket → collision.
6. Separate chaining: bucket = unsorted linked list of key/value nodes.
7. Load factor: n/m; resize on add when projected factor > 0.75 in lecture.
8. Resize: all keys are rehashed into new buckets, O(n).
9. Hash costs: add O(1) amortized; find/delete O(1) expected with good hashing and resizing.

Selection Sort, Quicksort & Heapsort

1. In the lecture's heapsort, insert 10, 7, 19, 5, 16 into an empty min-heap. What is the heap's final level-order array before removals?
2. What sorted output does repeated getMin() produce for those five values, and what is heapsort's overall Big-O runtime?
3. What does unsortedStart represent in selection sort?
4. After one selection sort pass on [10,7,19,5,16], what is the array?
5. What are selection sort's best, average and worst runtimes?
6. Why does an already sorted array not speed up selection sort?
7. Which element is chosen as pivot in the main quicksort lecture?
8. After a partition pass, what is guaranteed about the pivot?
9. What is the lecture's first partition result for [50,40,10,70,60,20,90,80,30]?
10. What do i and j track while partitioning?
11. What is the quicksort recursion base case?
12. What split pattern produces O(n²) quicksort performance?
13. What are randomized quicksort's expected and absolute worst-case runtimes?

Answer key

Hashing, Load Factor & Separate Chaining

1. Name the three Map ADT operations.
2. Under key % 10, what is the bucket for 87?
3. Do keys 11 and 71 collide in a 10-bucket table? Why?
4. What is stored in each node of a separate-chaining table?
5. Where do you search for key 14 in a table of 10 buckets using modulo?
6. What is the load factor for 75 keys and 100 buckets?
7. With 6 keys and 8 buckets, would adding a seventh cause a resize under the lecture's threshold?
8. Why does a resized table need to rehash all the keys?
9. What is the runtime of resizing a hash table?
10. Explain the difference between amortized O(1) add and expected O(1) find.
11. Name a system where the lecture suggests a balanced BST instead of a hash table.

Answer key