Priority queue with heaps in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a priority queue?

A priority queue is a special type of queue where each element has a priority. Elements with higher priority are served before elements with lower priority, unlike a normal queue which follows first-in-first-out order.

beginner

How does a heap help implement a priority queue?

A heap is a special tree-based structure that keeps the highest (or lowest) priority element at the root. This makes it easy and fast to get the element with the highest priority, which is needed for a priority queue.

beginner

What is the difference between a max-heap and a min-heap?

In a max-heap, the parent node is always greater than or equal to its children, so the largest element is at the root. In a min-heap, the parent node is always less than or equal to its children, so the smallest element is at the root.

intermediate

What is the time complexity to insert an element into a heap-based priority queue?

Inserting an element into a heap-based priority queue takes O(log n) time, where n is the number of elements. This is because the element may need to move up the tree to maintain the heap property.

intermediate

How do you remove the highest priority element from a heap?

To remove the highest priority element (the root), you replace it with the last element in the heap, then adjust the heap by moving this element down (heapify) to restore the heap property. This takes O(log n) time.

What does a priority queue always return when you remove an element?

A A random element

B The element that was added first

C The element with the lowest priority

D The element with the highest priority

A priority queue always removes and returns the element with the highest priority.

Which data structure is commonly used to efficiently implement a priority queue?

A Heap

B Linked list

C Array

D Stack

Heaps allow quick access to the highest priority element, making them ideal for priority queues.

In a max-heap, where is the largest element located?

A At the rightmost leaf

B At the leftmost leaf

C At the root

D At the middle level

The largest element in a max-heap is always at the root node.

What is the worst-case time complexity to remove the highest priority element from a heap?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Removing the root and restoring the heap property takes O(log n) time.

Which operation is NOT typical for a priority queue?

A Remove element with highest priority

B Remove element from the middle without priority consideration

C Peek at element with highest priority

D Insert element with priority

Priority queues do not support removing arbitrary elements without considering priority.

Explain how a heap maintains the priority queue property during insertion and removal.

Think about how the tree structure changes to keep the highest priority element at the root.

Describe the difference between a max-heap and a min-heap and how each relates to priority queues.

Consider which element you want to access first in your priority queue.

Practice

1. What is the main purpose of a priority queue implemented with a heap?

easy

A. To store elements in alphabetical order

B. To quickly access the highest priority element

C. To perform fast string searches

D. To sort elements in ascending order only

Solution

1. Step 1: Understand priority queue functionality

   A priority queue is designed to always provide quick access to the element with the highest priority.

2. Step 2: Recognize heap role in priority queue

   Heaps maintain the highest priority element at the top, enabling fast retrieval.

3. Final Answer:

   To quickly access the highest priority element -> Option B

4. Quick Check:

   Priority queue = fast highest priority access [OK]

Hint: Priority queue = fast access to top priority [OK]

Common Mistakes:

• Confusing priority queue with sorting
• Thinking it stores elements alphabetically
• Assuming it only sorts ascending

2. Which of the following is the correct way to insert an element into a max-heap based priority queue?

easy

A. Add element at the root and heapify up

B. Add element at the root and heapify down

C. Add element at the end and heapify down

D. Add element at the end and heapify up

Solution

1. Step 1: Understand insertion in max-heap

   New elements are added at the end (bottom level) to maintain complete tree property.

2. Step 2: Restore heap property by heapifying up

   Heapify up moves the new element up if it has higher priority than its parent.

3. Final Answer:

   Add element at the end and heapify up -> Option D

4. Quick Check:

   Insert = end + heapify up [OK]

Hint: Insert at end, then heapify up to fix heap [OK]

Common Mistakes:

• Adding element at root instead of end
• Heapifying down after insertion
• Confusing heapify directions

3. Given a max-heap priority queue with elements [40, 30, 20, 15, 10], what will be the heap array after extracting the max element?

medium

A. [30, 15, 20, 10]

B. [15, 30, 20, 10]

C. [20, 15, 10, 30]

D. [30, 10, 20, 15]

Solution

1. Step 1: Remove max element and replace with last

   Remove 40 (root), replace with last element 10: [10, 30, 20, 15]

2. Step 2: Heapify down to restore max-heap

   Compare 10 with children 30 and 20; swap with 30 (largest child): [30, 10, 20, 15]. Then compare 10 with 15; swap with 15: [30, 15, 20, 10].

3. Final Answer:

   [30, 15, 20, 10] -> Option A

4. Quick Check:

   Extract max + heapify down = [30, 15, 20, 10] [OK]

Hint: Replace root with last, then heapify down [OK]

Common Mistakes:

• Not swapping correctly during heapify down
• Forgetting to replace root with last element
• Confusing heapify up with heapify down

4. Identify the error in this pseudo-code for extracting the max from a max-heap priority queue:

extract_max(heap):
  max = heap[0]
  heap[0] = heap.pop()
  heapify_up(heap, 0)
  return max

medium

A. Should not assign max before popping

B. Should pop from the front instead of the end

C. Should call heapify_down instead of heapify_up

D. Should insert new element at the end before heapify

Solution

1. Step 1: Understand extract max steps

   Extract max removes root, replaces it with last element, then restores heap by heapifying down.

2. Step 2: Identify incorrect heapify call

   The code calls heapify_up, but after replacing root, heapify_down is needed to push the new root down if smaller.

3. Final Answer:

   Should call heapify_down instead of heapify_up -> Option C

4. Quick Check:

   Extract max = heapify down [OK]

Hint: Extract max uses heapify down, not up [OK]

Common Mistakes:

• Confusing heapify directions
• Popping from wrong end
• Misordering operations

5. You have a list of tasks with priorities: [(Task1, 5), (Task2, 3), (Task3, 5), (Task4, 2)]. Using a max-heap priority queue, which task will be extracted first and why?

hard

A. Task1, because it appears first among highest priority tasks

B. Task3, because it has the highest priority number

C. Task2, because it has the second highest priority

D. Task4, because it has the lowest priority

Solution

1. Step 1: Identify highest priority tasks

   Tasks with priority 5 are Task1 and Task3, highest among all.

2. Step 2: Understand heap extraction order for equal priorities

   Max-heap extracts highest priority; if priorities tie, extraction order depends on insertion order or heap structure. Usually, the first inserted among equals is extracted first.

3. Final Answer:

   Task1, because it appears first among highest priority tasks -> Option A

4. Quick Check:

   Highest priority + insertion order = Task1 first [OK]

Hint: Highest priority, then earliest inserted extracted first [OK]

Common Mistakes:

• Assuming any highest priority task is extracted first
• Ignoring insertion order for ties
• Picking lower priority tasks first