Функция heap.Pop

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

Синтаксис

heap.Pop(h)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

функцию heap.Init,
которая инициализирует кучу из слайса
функцию heap.Push,
которая добавляет элемент в кучу
функцию heap.Fix,
которая восстанавливает порядок кучи после изменения элемента
функцию heap.Remove,
которая удаляет элемент по индексу из кучи