Priority Queue Introduction and Concept in DSA Go - Build from Scratch

Priority Queue Introduction and Concept

📖 Scenario: You are managing a small hospital emergency room. Patients arrive with different urgency levels. You want to treat the most urgent patients first.

🎯 Goal: Build a simple priority queue using a list of patients with their urgency levels. Then, extract patients in order of urgency.

📋 What You'll Learn

Create a list of patients with their urgency levels

Add a variable to hold the number of patients

Sort patients by urgency level using a simple method

Print the patients in order from highest to lowest urgency

💡 Why This Matters

🌍 Real World

Priority queues are used in hospitals, task schedulers, and anywhere urgent tasks must be handled first.

💼 Career

Understanding priority queues helps in roles like software development, system design, and operations where task prioritization is key.

1

Create the list of patients with urgency levels

Create a variable called patients as a slice of structs with fields name (string) and urgency (int). Add these exact entries: {"John", 3}, {"Alice", 5}, {"Bob", 2}, {"Diana", 4}.

DSA Go

// Define the patients slice with name and urgency
// Your code here

Hint

Use a struct type Patient with fields name and urgency. Then create a slice patients with the given entries.

2

Add a variable for the number of patients

Add a variable called count and set it to the length of the patients slice using the len function.

DSA Go

package main

import "fmt"

type Patient struct {
    name    string
    urgency int
}

func main() {
    patients := []Patient{
        {"John", 3},
        {"Alice", 5},
        {"Bob", 2},
        {"Diana", 4},
    }
    // Add count variable here
    // Your code here
}

Hint

Use len(patients) to get the number of patients and assign it to count.

3

Sort patients by urgency level

Use a simple bubble sort with a for loop and nested for loop to sort the patients slice in descending order by urgency. Swap patients when the next patient has higher urgency.

DSA Go

package main

import "fmt"

type Patient struct {
    name    string
    urgency int
}

func main() {
    patients := []Patient{
        {"John", 3},
        {"Alice", 5},
        {"Bob", 2},
        {"Diana", 4},
    }
    count := len(patients)
    // Sort patients by urgency descending
    // Your code here
}

Hint

Use nested loops to compare adjacent patients and swap them if the next has higher urgency. This sorts the slice in descending order.

4

Print patients in order of urgency

Use a for loop with variable i from 0 to count to print each patient's name and urgency in the format: "Name: [name], Urgency: [urgency]".

DSA Go

package main

import "fmt"

type Patient struct {
    name    string
    urgency int
}

func main() {
    patients := []Patient{
        {"John", 3},
        {"Alice", 5},
        {"Bob", 2},
        {"Diana", 4},
    }
    count := len(patients)

    for i := 0; i < count-1; i++ {
        for j := 0; j < count-1-i; j++ {
            if patients[j].urgency < patients[j+1].urgency {
                patients[j], patients[j+1] = patients[j+1], patients[j]
            }
        }
    }
    // Print patients in order
    // Your code here
}

Hint

Use fmt.Printf inside a loop to print each patient's name and urgency in the required format.

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