Интерфейс heap.Interface

Интерфейс heap.Interface определяет набор методов, которые должна реализовать пользовательская структура данных для работы с кучей (heap) в Go. Он включает методы стандартного интерфейса sort.Interface (Len, Less, Swap) и дополнительные методы Push и Pop для добавления и удаления элементов. Первый параметр метода Push - это интерфейс, в который мы добавляем элемент, второй параметр - добавляемый элемент. Метод Pop принимает интерфейс и возвращает удаленный элемент.

Синтаксис

gotype Interface interface {
  sort.Interface
  Push(x any)
  Pop() any
}

Пример

Давайте создадим структуру для хранения целых чисел в виде минимальной кучи:

gopackage 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)
}

Результат выполнения кода:

go[1 1 2 3 5 9 4 6]

Пример

Давайте добавим элемент в кучу и извлечем минимальный элемент:

gopackage 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)
}

Результат выполнения кода:

go1
[2 3 5 8 9]

Пример

Давайте реализуем кучу для пользовательской структуры, сортируя по полю Priority:

gopackage 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)
  }
}

Результат выполнения кода:

go"task1: 1"
"task2: 2"
"task3: 3"
"task5: 5"

Смотрите также