Функция heap.Init

Функция heap.Init инициализирует срез таким образом, чтобы он удовлетворял свойствам кучи. Она принимает один параметр - интерфейс heap.Interface, который должен быть реализован типом среза. После вызова heap.Init элементы среза переупорядочиваются так, чтобы выполнялось свойство кучи: для минимальной кучи каждый родительский элемент меньше или равен своим дочерним элементам.

Синтаксис

heap.Init(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, 3, 8, 1, 9}
	heap.Init(h)
	fmt.Println(*h)
}

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

[1 3 5 8 9]

После инициализации первый элемент среза становится наименьшим в куче, что соответствует свойству минимальной кучи.

Пример с добавлением элементов

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

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{10, 4, 7, 2, 6}
	heap.Init(h)
	fmt.Println("After init:", *h)

	heap.Push(h, 1)
	fmt.Println("After push:", *h)
	heap.Init(h)
	fmt.Println("After reinit:", *h)
}

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

"After init: [2 4 7 10 6]"
"After push: [2 4 7 10 6 1]"
"After reinit: [1 4 2 10 6 7]"

Обратите внимание: после прямого добавления элемента через heap.Push свойство кучи временно нарушается, поэтому требуется повторная инициализация.

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

Давайте создадим максимальную кучу, изменив функцию Less:

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int

func (h MaxHeap) Len() int		   { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)	  { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

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

func main() {
	h := &MaxHeap{5, 3, 8, 1, 9}
	heap.Init(h)
	fmt.Println(*h)
}

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

[9 8 3 1 5]

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

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

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