Функция heap.Fix

Функция heap.Fix восстанавливает свойства кучи после изменения значения элемента. Она принимает два параметра: первый параметр — это интерфейс heap.Interface, представляющий кучу, второй параметр — индекс элемента, значение которого было изменено. Функция переупорядочивает кучу, перемещая измененный элемент вверх или вниз по дереву в зависимости от его нового значения.

Синтаксис

goheap.Fix(h, i)

Пример

Создадим минимальную кучу из целых чисел и увеличим значение корневого элемента, а затем восстановим свойства кучи с помощью heap.Fix:

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)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  h := &IntHeap{1, 3, 5, 7, 9}
  heap.Init(h)

  // Изменяем корневой элемент
  (*h)[0] = 10
  heap.Fix(h, 0)

  fmt.Println(*h)
}

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

go[3 7 5 10 9]

После увеличения корневого элемента с 1 до 10 куча была восстановлена, и новый корень стал равен 3.

Пример

Уменьшим значение элемента в середине кучи и восстановим свойства с помощью heap.Fix:

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)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func main() {
  h := &IntHeap{1, 3, 5, 7, 9, 2, 4}
  heap.Init(h)

  // Изменяем элемент по индексу 2
  (*h)[2] = 0
  heap.Fix(h, 2)

  fmt.Println(*h)
}

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

go[0 3 1 7 9 2 5]

Уменьшенный элемент был перемещен вверх к корню кучи, сохраняя свойство минимальной кучи.

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