Функция heap.Init

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

Синтаксис

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

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

go[1 3 5 8 9]

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

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

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

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

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

go"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:

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

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

go[9 8 3 1 5]

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

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