Что такое куча (Heap) в контексте структур данных?

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

Ключевые характеристики:

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

Пример min-heap на Java с использованием PriorityQueue:

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // PriorityQueue по умолчанию реализует min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(3);

        // Извлечение и удаление минимального элемента
        System.out.println(minHeap.poll()); // Вывод: 1
        System.out.println(minHeap.peek()); // Вывод: 3 (новый минимум без удаления)
    }
}