Priority queue with heaps in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does a binary heap maintain the priority queue property?

Consider a binary heap used to implement a priority queue. Which statement best describes how it maintains the priority queue property?

A The heap stores elements in sorted order from left to right at each level.

B The heap keeps the smallest (or largest) element at the root, and each parent node is smaller (or larger) than its children.

C The heap uses a linked list to keep elements sorted by priority.

D The heap randomly arranges elements but searches linearly to find the highest priority.

💡 Hint

Think about how the root element relates to its children in a heap.

A binary heap maintains the priority queue property by ensuring the root node is always the smallest (min-heap) or largest (max-heap) element. Each parent node respects this order relative to its children, but the elements are not fully sorted.

🚀 Application

intermediate

What is the time complexity of inserting an element into a binary heap?

When inserting a new element into a binary heap used as a priority queue, what is the time complexity of this operation?

A O(1) because the element is added at the end without rearrangement.

B O(n) because the entire heap must be rebuilt after insertion.

C O(log n) because the element may need to be moved up the tree to maintain heap property.

D O(n log n) because insertion requires sorting all elements.

💡 Hint

Consider how the heap property is restored after adding a new element.

Insertion adds the element at the bottom and then 'bubbles up' to restore the heap property. This bubbling up takes at most the height of the heap, which is log n for a binary heap.

🔍 Analysis

advanced

What is the output of removing the root from this min-heap?

Given the min-heap represented as an array: [3, 5, 8, 10, 15, 12], what is the array after removing the root element?

Data Structures Theory

Initial heap array: [3, 5, 8, 10, 15, 12]
Operation: Remove root (minimum element)

A [5, 10, 8, 15, 12]

B [8, 10, 12, 15, 5]

C [8, 5, 12, 10, 15]

D [5, 10, 8, 12, 15]

💡 Hint

After removing the root, replace it with the last element and then 'bubble down' to restore the heap.

Remove 3 (root). Replace root with last element 12: [12, 5, 8, 10, 15]. Bubble down 12: swap with 5 → [5, 12, 8, 10, 15]. Then swap 12 with 10 → [5, 10, 8, 12, 15].

❓ Comparison

advanced

Which data structure is more efficient for priority queue operations?

Compare a binary heap and a sorted array for implementing a priority queue. Which statement is true about their efficiency?

A Binary heap has O(log n) insertion and O(log n) removal; sorted array has O(n) insertion and O(1) removal.

B Binary heap has O(1) insertion and O(n) removal; sorted array has O(log n) insertion and O(log n) removal.

C Binary heap and sorted array both have O(n) insertion and removal times.

D Binary heap has O(n) insertion and O(1) removal; sorted array has O(log n) insertion and O(n) removal.

💡 Hint

Think about how insertion and removal work in both data structures.

Binary heap inserts in O(log n) by bubbling up and removes root in O(log n) by bubbling down. Sorted array requires O(n) to insert (to keep sorted) but removal of highest priority (first element) is O(1).

❓ Reasoning

expert

Why is a binary heap preferred over a balanced binary search tree for a priority queue?

Both binary heaps and balanced binary search trees (BSTs) can implement priority queues. Why is a binary heap often preferred?

A Binary heaps have simpler structure and faster average insertion and removal times for priority queue operations.

B Balanced BSTs cannot maintain order of elements, so they are unsuitable for priority queues.

C Binary heaps use more memory but provide constant time search for any element.

D Balanced BSTs require less maintenance and have faster insertion than binary heaps.

💡 Hint

Consider the complexity and structure simplicity of both data structures.

Binary heaps are simpler to implement and provide O(log n) insertion and removal with less overhead than balanced BSTs, which maintain full order but have more complex balancing operations.

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