Интерфейс heap.Interface
Интерфейс heap.Interface определяет набор методов, которые должна реализовать пользовательская структура данных для работы с кучей (heap) в Go. Он включает методы стандартного интерфейса sort.Interface (Len, Less, Swap) и дополнительные методы Push и Pop для добавления и удаления элементов. Первый параметр метода Push - это интерфейс, в который мы добавляем элемент, второй параметр - добавляемый элемент. Метод Pop принимает интерфейс и возвращает удаленный элемент.
Синтаксис
type Interface interface {
sort.Interface
Push(x any)
Pop() any
}
Пример
Давайте создадим структуру для хранения целых чисел в виде минимальной кучи:
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 any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
item := old[n-1]
*h = old[0 : n-1]
return item
}
func main() {
h := &IntHeap{3, 1, 4, 1, 5, 9, 2, 6}
heap.Init(h)
fmt.Println(*h)
}
Результат выполнения кода:
[1 1 2 3 5 9 4 6]
Пример
Давайте добавим элемент в кучу и извлечем минимальный элемент:
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 any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
item := old[n-1]
*h = old[0 : n-1]
return item
}
func main() {
h := &IntHeap{5, 3, 8, 1, 9}
heap.Init(h)
heap.Push(h, 2)
min := heap.Pop(h).(int)
fmt.Println(min)
fmt.Println(*h)
}
Результат выполнения кода:
1
[2 3 5 8 9]
Пример
Давайте реализуем кучу для пользовательской структуры, сортируя по полю Priority:
package main
import (
"container/heap"
"fmt"
)
type Item struct {
Value string
Priority 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
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x any) {
*pq = append(*pq, x.(Item))
}
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func main() {
pq := &PriorityQueue{
{Value: "task3", Priority: 3},
{Value: "task1", Priority: 1},
{Value: "task5", Priority: 5},
}
heap.Init(pq)
heap.Push(pq, Item{Value: "task2", Priority: 2})
for pq.Len() > 0 {
item := heap.Pop(pq).(Item)
fmt.Printf("%s: %d\n", item.Value, item.Priority)
}
}
Результат выполнения кода:
"task1: 1"
"task2: 2"
"task3: 3"
"task5: 5"
