Priority Queue Introduction and Concept in DSA Go

Mental Model

A priority queue is a special list where each item has a rank, and the highest rank item always comes out first.

Analogy: Imagine a line at a hospital emergency room where patients with more serious conditions get treated before others, no matter when they arrived.

Priority Queue:
[5] -> [3] -> [4] -> [1] -> null
↑ highest priority at front

Dry Run Walkthrough

Input: Insert values 3, 5, 1, 4 into an empty priority queue

Goal: Keep the queue ordered so the highest value is always at the front

Step 1: Insert 3 into empty queue

[3] -> null

Why: First item becomes the front since queue was empty

Step 2: Insert 5, which is higher than 3, so put it at front

[5] -> [3] -> null

Why: Higher priority items go to the front

Step 3: Insert 1, which is lower than 3, so put it at the end

[5] -> [3] -> [1] -> null

Why: Lower priority items go behind higher ones

Step 4: Insert 4, which fits between 5 and 3

[5] -> [4] -> [3] -> [1] -> null

Why: Keep queue sorted by priority descending

Result:

[5] -> [4] -> [3] -> [1] -> null

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	value    int
	priority int
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority > pq[j].priority // higher priority first
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	item.index = len(*pq)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return item
}

func main() {
	pq := make(PriorityQueue, 0)
	heap.Init(&pq)

	values := []int{3, 5, 1, 4}
	for _, v := range values {
		heap.Push(&pq, &Item{
			value:    v,
			priority: v,
		})
	}

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Print(item.value)
		if pq.Len() > 0 {
			fmt.Print(" -> ")
		}
	}
	fmt.Println(" -> null")
}

return pq[i].priority > pq[j].priority // higher priority first

compare priorities to keep highest priority at front

heap.Push(&pq, &Item{value: v, priority: v})

insert new item with its priority

item := heap.Pop(&pq).(*Item)

remove highest priority item from queue

Output

5 -> 4 -> 3 -> 1 -> null

Complexity Analysis

Time: O(log n) for insert and remove because heap adjusts in logarithmic steps

Space: O(n) because all items are stored in the heap array

vs Alternative: Compared to sorting the whole list each time (O(n log n)), heap keeps order efficiently with O(log n) per operation

Edge Cases

empty queue

pop returns nothing, no error

DSA Go

for pq.Len() > 0 {

all items have same priority

items come out in insertion order or heap order

DSA Go

return pq[i].priority > pq[j].priority

When to Use This Pattern

When you need to always get the highest or lowest priority item quickly, use a priority queue because it keeps data sorted efficiently.

Common Mistakes

Mistake: Inverting the priority comparison so lowest priority comes first by mistake
Fix: Use '>' in Less() method to ensure highest priority is first

Summary

A priority queue stores items so the highest priority item is always removed first.

Use it when you need quick access to the most important item, like task scheduling.

The key is to keep the structure ordered by priority, not by insertion order.

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