Функция heap.Fix

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

Синтаксис

heap.Fix(h, i)

Пример

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

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

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

[3 7 5 10 9]

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

Пример

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

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

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

[0 3 1 7 9 2 5]

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

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

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