Priority Queue Introduction and Concept in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this priority queue after insertions?

Consider a min-priority queue where smaller numbers have higher priority. Insert the numbers 5, 3, 8, 1 in this order. What is the state of the queue after all insertions?

DSA Go

Insert 5
Insert 3
Insert 8
Insert 1
Print queue

A 1 -> 3 -> 5 -> 8 -> null

B 8 -> 5 -> 3 -> 1 -> null

C 5 -> 3 -> 8 -> 1 -> null

D 3 -> 1 -> 5 -> 8 -> null

💡 Hint

Remember, in a min-priority queue, the smallest element is always at the front.

After inserting 5, 3, 8, and 1, the min-priority queue orders elements so that the smallest is first. The queue becomes 1 -> 3 -> 5 -> 8 -> null.

❓ Predict Output

intermediate

What is the output after removing the highest priority element?

Given a max-priority queue with elements 10, 20, 15 inserted in that order, what is the queue state after removing the highest priority element once?

DSA Go

Insert 10
Insert 20
Insert 15
Remove highest priority
Print queue

A 15 -> 10 -> null

B 20 -> 15 -> 10 -> null

C 10 -> 15 -> null

D 15 -> 20 -> null

💡 Hint

In a max-priority queue, the largest element is removed first.

Initially, the queue is 20 -> 15 -> 10. Removing the highest priority (20) leaves 15 -> 10.

🔧 Debug

advanced

What error does this Go code cause when using a priority queue?

Analyze the following Go code snippet using container/heap package. What error will it produce when run?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("min: %d\n", (*h)[0])
	for i := 0; i < 4; i++ {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

A panic: interface conversion error

B runtime error: index out of range

C no error, prints all elements correctly

D compilation error: missing import

💡 Hint

Check the loop condition when popping elements from the heap.

The loop runs from i = 0 to i = h.Len() inclusive, but h.Len() decreases with each pop. This causes an index out of range error.

🧠 Conceptual

advanced

Which property does a binary heap maintain?

A binary heap is a common way to implement a priority queue. Which property must it always maintain?

A The tree nodes are linked in a circular doubly linked list

B The tree is a full binary tree and all leaves are at the same depth

C The tree is balanced and sorted in ascending order from left to right

D The tree is a complete binary tree and each parent node is smaller (min-heap) or larger (max-heap) than its children

💡 Hint

Think about the shape and order properties of heaps.

A binary heap must be a complete binary tree and maintain the heap property where parents are ordered relative to children.

🚀 Application

expert

What is the time complexity of inserting n elements into an empty priority queue implemented with a binary heap?

You insert n elements one by one into an empty binary heap priority queue. What is the total time complexity of all insertions?

A O(n)

B O(log n)

C O(n log n)

D O(n^2)

💡 Hint

Each insertion takes O(log n) time. Consider n insertions.

Each insertion into a binary heap takes O(log n) time. Doing this n times results in O(n log n) total time.

Practice

1. What is the main feature of a priority queue compared to a regular queue?

easy

A. It does not allow insertion after creation

B. Elements are always dequeued in the order they were inserted

C. Elements are dequeued based on their priority, not just order of insertion

D. It only stores elements of the same value

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on priority, not just insertion order.

3. Final Answer:

   Elements are dequeued based on their priority, not just order of insertion -> Option C

4. Quick Check:

   Priority queue = priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue only stores unique values
• Assuming insertion order always matters

2. Which of the following is the correct way to declare a priority queue in Go using the container/heap package?

easy

A. var pq = &PriorityQueue{} // where PriorityQueue implements heap.Interface

B. var pq heap.Interface

C. pq := make([]int, 0) // simple slice, no heap

D. var pq = new(priorityQueue) // without implementing heap.Interface

Solution

1. Step 1: Recognize Go heap usage

   Go's container/heap requires a type implementing heap.Interface.

2. Step 2: Correct declaration

   Creating a pointer to a struct implementing heap.Interface is correct.

3. Final Answer:

   var pq = &PriorityQueue{} // where PriorityQueue implements heap.Interface -> Option A

4. Quick Check:

   PriorityQueue struct + heap.Interface = correct declaration [OK]

Hint: Use struct pointer implementing heap.Interface for priority queue [OK]

Common Mistakes:

• Declaring slice only without heap.Interface
• Using heap.Interface type directly without struct
• Not using pointer receiver for heap methods

3. What will be the output of the following Go code snippet?

package main

import (
  "container/heap"
  "fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  h := &IntHeap{2, 1, 5}
  heap.Init(h)
  heap.Push(h, 3)
  fmt.Println(heap.Pop(h))
}

medium

A. 1

B. 5

C. 2

D. 3

Solution

1. Step 1: Understand heap type and ordering

   The Less function returns h[i] > h[j], so this is a max-heap (largest element on top).

2. Step 2: Trace heap operations

   Initial heap: [2,1,5]. After heap.Init, heap property is established. Push 3 adds 3. The max element is 5, so heap.Pop returns 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max-heap pop returns largest = 5 [OK]

Hint: Check Less() to know max or min heap, then pop returns max/min [OK]

Common Mistakes:

• Assuming min-heap by default
• Confusing Push and Pop order
• Not tracing heap.Init effect

4. Identify the error in the following Go code snippet that uses a priority queue:

package main

import (
  "container/heap"
  "fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  h := IntHeap{3, 2, 1}
  heap.Init(&h)
  heap.Push(&h, 4)
  fmt.Println(heap.Pop(&h))
}

medium

A. heap.Pop called with value instead of pointer

B. Push method does not append correctly

C. Less method should use > for max-heap

D. Swap method has wrong indices

Solution

1. Step 1: Check heap.Pop usage

   heap.Pop requires a pointer to the heap, but code calls heap.Pop(h) passing value.

2. Step 2: Confirm other methods

   Push, Less, Swap are correctly defined. The error is in calling heap.Pop without &.

3. Final Answer:

   heap.Pop called with value instead of pointer -> Option A

4. Quick Check:

   heap.Pop needs pointer argument [OK]

Hint: heap.Pop needs pointer, not value [OK]

Common Mistakes:

• Calling heap.Pop with value instead of pointer
• Confusing Less method for error
• Ignoring method signatures for Push/Pop

5. You want to implement a task scheduler using a priority queue in Go, where tasks with lower integer priority values run first. Which of the following Less method implementations correctly creates a min-heap for this purpose?

hard

A. func (h TaskHeap) Less(i, j int) bool { return h[i].priority > h[j].priority }

B. func (h TaskHeap) Less(i, j int) bool { return h[i].priority >= h[j].priority }

C. func (h TaskHeap) Less(i, j int) bool { return h[i].priority == h[j].priority }

D. func (h TaskHeap) Less(i, j int) bool { return h[i].priority < h[j].priority }

Solution

1. Step 1: Understand min-heap property

   Min-heap means the smallest priority value is at the top, so Less should return true if i's priority is less than j's.

2. Step 2: Analyze options

   func (h TaskHeap) Less(i, j int) bool { return h[i].priority < h[j].priority } returns true if h[i].priority < h[j].priority, which is correct for min-heap. Others do not correctly implement min-heap ordering.

3. Final Answer:

   func (h TaskHeap) Less(i, j int) bool { return h[i].priority < h[j].priority } -> Option D

4. Quick Check:

   Min-heap Less returns true if i priority less than j [OK]

Hint: Min-heap Less returns true if i < j priority [OK]

Common Mistakes:

• Using > instead of < for min-heap
• Using equality in Less method
• Using >= which breaks heap property