Функция heap.Pop

Функция heap.Pop извлекает и возвращает минимальный элемент из кучи, представленной слайсом, который реализует интерфейс heap.Interface. После извлечения элемента куча перестраивается для сохранения свойства упорядоченности. В первый параметр мы передаем интерфейс кучи (слайс с реализованными методами Len, Less, Swap, Push и Pop). Функция возвращает извлеченный элемент типа interface{}, который необходимо привести к нужному типу.

Синтаксис

goheap.Pop(h)

Пример минимальной кучи

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

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 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{5, 2, 8, 1, 9}
  heap.Init(h)

  min := heap.Pop(h)
  fmt.Printf("Извлеченный элемент: %d\n", min)
  fmt.Printf("Куча после извлечения: %v\n", *h)
}

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

go"Извлеченный элемент: 1"
"Куча после извлечения: [2 5 8 9]"

Пример с пользовательским типом

Рассмотрим извлечение элемента из кучи, содержащей структуры с приоритетами:

gopackage main

import (
  "container/heap"
  "fmt"
)

type Task struct {
  priority int
  name   string
}

type TaskHeap []Task

func (h TaskHeap) Len() int { return len(h) }
func (h TaskHeap) Less(i, j int) bool {
  return h[i].priority < h[j].priority
}
func (h TaskHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *TaskHeap) Push(x interface{}) {
  *h = append(*h, x.(Task))
}

func (h *TaskHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  tasks := &TaskHeap{
    {priority: 3, name: "low"},
    {priority: 1, name: "high"},
    {priority: 2, name: "medium"},
  }
  heap.Init(tasks)

  topTask := heap.Pop(tasks).(Task)
  fmt.Printf("Извлечена задача: %+v\n", topTask)
  fmt.Printf("Оставшиеся задачи: %+v\n", *tasks)
}

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

go"Извлечена задача: {priority:1 name:high}"
"Оставшиеся задачи: [{priority:2 name:medium} {priority:3 name:low}]"

Пример последовательного извлечения

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

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 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{7, 3, 9, 1, 5}
  heap.Init(h)

  fmt.Println("Извлечение всех элементов:")
  for h.Len() > 0 {
    val := heap.Pop(h).(int)
    fmt.Printf("%d ", val)
  }
  fmt.Println()
}

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

go"Извлечение всех элементов:"
"1 3 5 7 9 "

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