Что такое ‘куча’ (heap) как структура данных? Каковы её преимущества, недостатки и как она реализована в Go?

Куча (Heap) — это древовидная структура данных, которая удовлетворяет свойству кучи: для min-heap (минимальной кучи) значение в любом узле меньше или равно значениям его потомков. Для max-heap (максимальной кучи) — наоборот. Чаще всего реализуется на основе массива.

Преимущества:

• Быстрый доступ к экстремуму: Получение минимального (в min-heap) или максимального (в max-heap) элемента происходит за константное время O(1).
• Эффективные вставка и удаление: Операции вставки нового элемента и удаления экстремума выполняются за логарифмическое время O(log n).
• Основа для алгоритмов: Является ключевой структурой для реализации приоритетных очередей (Priority Queue) и эффективных алгоритмов, таких как сортировка кучей (Heapsort) и алгоритм Дейкстры.

Недостатки:

• Медленный поиск: Поиск произвольного элемента (не экстремума) требует полного перебора за линейное время O(n).
• Сложность поддержания инварианта: После каждой модификации необходимо выполнять операции heapify-up или heapify-down для сохранения свойства кучи, что усложняет реализацию по сравнению с простыми массивами или списками.

Реализация в Go:

В Go нет встроенного типа heap, но есть пакет container/heap, который предоставляет алгоритмы для работы с любой структурой, реализующей интерфейс heap.Interface. Этот интерфейс включает в себя sort.Interface (Len, Less, Swap) и два дополнительных метода: Push и Pop.

Пример реализации и использования минимальной кучи:

package main

import (
    "container/heap"
    "fmt"
)

// MinHeap реализует heap.Interface
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] } // < для min-heap
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push добавляет элемент в кучу
func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(int))
}

// Pop удаляет и возвращает минимальный элемент
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    // Создаем и инициализируем кучу
    h := &MinHeap{2, 1, 5, 9, 4}
    heap.Init(h)
    fmt.Printf("Инициализированная куча: %vn", *h)

    // Добавляем новый элемент
    heap.Push(h, 0)
    fmt.Printf("После добавления 0: %vn", *h)

    // Извлекаем минимальный элемент
    min := heap.Pop(h)
    fmt.Printf("Минимальный элемент: %dn", min)
    fmt.Printf("Куча после извлечения: %vn", *h)
}