What is a priority queue and how can it be implemented?

A priority queue is a data structure in which each element has a priority, and elements are extracted in order of decreasing (or increasing) priority, not just in the order of insertion.

In Go, it can be implemented using the container/heap package, which provides an interface for creating a heap. A heap is an efficient structure for implementing a priority queue.

Example implementation of a priority queue in Go:

package main

import (
    "container/heap"
    "fmt"
)

// Element with priority
type Item struct {
    value    string
    priority int
    index    int // index in the heap
}

// Type implementing heap.Interface
type PriorityQueue []*Item

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

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

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{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

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

    heap.Push(&pq, &Item{value: "task1", priority: 3})
    heap.Push(&pq, &Item{value: "task2", priority: 5})
    heap.Push(&pq, &Item{value: "task3", priority: 1})

    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("Processing %s with priority %d\n", item.value, item.priority)
    }
}

In this example, tasks with higher priority are processed first.