Очередь с приоритетом — это структура данных, в которой каждый элемент имеет приоритет, и элементы извлекаются в порядке убывания (или возрастания) приоритета, а не просто по порядку добавления.

В Go её можно реализовать с помощью пакета container/heap, который предоставляет интерфейс для создания кучи (heap). Куча — это эффективная структура для реализации очереди с приоритетом.

Пример реализации очереди с приоритетом в Go:

package main

import (
    "container/heap"
    "fmt"
)

// Элемент с приоритетом
type Item struct {
    value    string
    priority int
    index    int // индекс в куче
}

// Тип, реализующий heap.Interface
type PriorityQueue []*Item

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

func (pq PriorityQueue) Less(i, j int) bool {
    // Чем выше priority, тем выше приоритет
    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)
    }
}

В этом примере задачи с более высоким приоритетом обрабатываются раньше.

Что такое очередь с приоритетом и как ее можно реализовать?