Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 8.1 Куча

Куча (heap) - это полное двоичное дерево, удовлетворяющее определенным условиям. Основных типов кучи два, как показано на рисунке 8-1.

- Минимальная куча (min heap): значение любого узла \(\leq\) значения его дочерних узлов.
- Максимальная куча (max heap): значение любого узла \(\geq\) значения его дочерних узлов.

Рисунок 8-1 Минимальная куча и максимальная куча

Куча, являясь частным случаем полного двоичного дерева, обладает следующими свойствами.

- Узлы самого нижнего уровня заполняются слева, а все остальные уровни заполнены полностью.
- Корневой узел двоичного дерева мы называем вершиной кучи, а самый правый узел нижнего уровня - основанием кучи.
- Для максимальной (минимальной) кучи значение элемента на вершине, то есть у корневого узла, является максимальным (минимальным).

## 8.1.1 Распространенные операции с кучей

Нужно отметить, что многие языки программирования предоставляют не саму кучу, а очередь с приоритетом (priority queue) - абстрактную структуру данных, определяемую как очередь, в которой элементы извлекаются в соответствии с приоритетом.

На практике куча обычно используется для реализации очереди с приоритетом, а максимальная куча эквивалентна очереди с приоритетом, в которой элементы извлекаются по убыванию. С точки зрения использования очередь с приоритетом и куча могут считаться эквивалентными структурами данных. Поэтому в этой книге мы не будем специально различать их и в дальнейшем будем единообразно называть кучей.

Распространенные операции с кучей приведены в таблице 8-1. Конкретные имена методов зависят от языка программирования.

Таблица 8-1 Эффективность операций с кучей

Имя метода | Описание | Временная сложность
--- | --- | ---
`push()` | Поместить элемент в кучу | \(O(\log n)\)
`pop()` | Извлечь элемент с вершины кучи | \(O(\log n)\)
`peek()` | Получить доступ к вершине кучи (для max / min кучи это соответственно максимум / минимум) | \(O(1)\)
`size()` | Получить число элементов в куче | \(O(1)\)
`isEmpty()` | Проверить, пуста ли куча | \(O(1)\)

В реальных приложениях мы можем напрямую использовать классы кучи, предоставляемые языком программирования, или классы очереди с приоритетом.

Подобно сортировкам «по возрастанию» и «по убыванию», мы можем переключаться между «минимальной кучей» и «максимальной кучей», изменяя `flag` или модифицируя `Comparator` . Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
heap.py

    # Инициализация минимальной кучи
    min_heap, flag = [], 1
    # Инициализация максимальной кучи
    max_heap, flag = [], -1

    # Модуль heapq в Python по умолчанию реализует минимальную кучу
    # Если инвертировать знак элемента перед добавлением, то отношение порядка перевернется и так реализуется максимальная куча
    # В этом примере flag = 1 соответствует минимальной куче, а flag = -1 - максимальной

    # Добавление элементов в кучу
    heapq.heappush(max_heap, flag * 1)
    heapq.heappush(max_heap, flag * 3)
    heapq.heappush(max_heap, flag * 2)
    heapq.heappush(max_heap, flag * 5)
    heapq.heappush(max_heap, flag * 4)

    # Получение элемента на вершине кучи
    peek: int = flag * max_heap[0] # 5

    # Извлечение элемента с вершины кучи
    # Извлеченные элементы образуют последовательность по убыванию
    val = flag * heapq.heappop(max_heap) # 5
    val = flag * heapq.heappop(max_heap) # 4
    val = flag * heapq.heappop(max_heap) # 3
    val = flag * heapq.heappop(max_heap) # 2
    val = flag * heapq.heappop(max_heap) # 1

    # Получение размера кучи
    size: int = len(max_heap)

    # Проверка, пуста ли куча
    is_empty: bool = not max_heap

    # Построение кучи из входного списка
    min_heap: list[int] = [1, 3, 2, 5, 4]
    heapq.heapify(min_heap)

heap.cpp

    /* Инициализация кучи */
    // Инициализация минимальной кучи
    priority_queue<int, vector<int>, greater<int>> minHeap;
    // Инициализация максимальной кучи
    priority_queue<int, vector<int>, less<int>> maxHeap;

    /* Добавление элементов в кучу */
    maxHeap.push(1);
    maxHeap.push(3);
    maxHeap.push(2);
    maxHeap.push(5);
    maxHeap.push(4);

    /* Получение элемента на вершине кучи */
    int peek = maxHeap.top(); // 5

    /* Извлечение элемента с вершины кучи */
    // Извлеченные элементы образуют последовательность по убыванию
    maxHeap.pop(); // 5
    maxHeap.pop(); // 4
    maxHeap.pop(); // 3
    maxHeap.pop(); // 2
    maxHeap.pop(); // 1

    /* Получение размера кучи */
    int size = maxHeap.size();

    /* Проверка, пуста ли куча */
    bool isEmpty = maxHeap.empty();

    /* Построение кучи из входного списка */
    vector<int> input{1, 3, 2, 5, 4};
    priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

heap.java

    /* Инициализация кучи */
    // Инициализация минимальной кучи
    Queue<Integer> minHeap = new PriorityQueue<>();
    // Инициализация максимальной кучи (достаточно изменить Comparator через lambda)
    Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

    /* Добавление элементов в кучу */
    maxHeap.offer(1);
    maxHeap.offer(3);
    maxHeap.offer(2);
    maxHeap.offer(5);
    maxHeap.offer(4);

    /* Получение элемента на вершине кучи */
    int peek = maxHeap.peek(); // 5

    /* Извлечение элемента с вершины кучи */
    // Извлеченные элементы образуют последовательность по убыванию
    peek = maxHeap.poll(); // 5
    peek = maxHeap.poll(); // 4
    peek = maxHeap.poll(); // 3
    peek = maxHeap.poll(); // 2
    peek = maxHeap.poll(); // 1

    /* Получение размера кучи */
    int size = maxHeap.size();

    /* Проверка, пуста ли куча */
    boolean isEmpty = maxHeap.isEmpty();

    /* Построение кучи из входного списка */
    minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

heap.cs

    /* Инициализация кучи */
    // Инициализация минимальной кучи
    PriorityQueue<int, int> minHeap = new();
    // Инициализация максимальной кучи (достаточно изменить Comparer через lambda)
    PriorityQueue<int, int> maxHeap = new(Comparer<int>.Create((x, y) => y.CompareTo(x)));

    /* Добавление элементов в кучу */
    maxHeap.Enqueue(1, 1);
    maxHeap.Enqueue(3, 3);
    maxHeap.Enqueue(2, 2);
    maxHeap.Enqueue(5, 5);
    maxHeap.Enqueue(4, 4);

    /* Получение элемента на вершине кучи */
    int peek = maxHeap.Peek();//5

    /* Извлечение элемента с вершины кучи */
    // Извлеченные элементы образуют последовательность по убыванию
    peek = maxHeap.Dequeue();  // 5
    peek = maxHeap.Dequeue();  // 4
    peek = maxHeap.Dequeue();  // 3
    peek = maxHeap.Dequeue();  // 2
    peek = maxHeap.Dequeue();  // 1

    /* Получение размера кучи */
    int size = maxHeap.Count;

    /* Проверка, пуста ли куча */
    bool isEmpty = maxHeap.Count == 0;

    /* Построение кучи из входного списка */
    minHeap = new PriorityQueue<int, int>([(1, 1), (3, 3), (2, 2), (5, 5), (4, 4)]);

heap.go

    // В Go можно построить целочисленную максимальную кучу, реализовав heap.Interface
    // Для реализации heap.Interface также нужно реализовать sort.Interface
    type intHeap []any

    // Метод Push из heap.Interface, реализует добавление элемента в кучу
    func (h *intHeap) Push(x any) {
        // Push и Pop используют pointer receiver
        // Потому что они не только изменяют содержимое среза, но и его длину
        *h = append(*h, x.(int))
    }

    // Метод Pop из heap.Interface, реализует извлечение элемента с вершины кучи
    func (h *intHeap) Pop() any {
        // Извлекаемый элемент хранится в конце
        last := (*h)[len(*h)-1]
        *h = (*h)[:len(*h)-1]
        return last
    }

    // Метод Len из sort.Interface
    func (h *intHeap) Len() int {
        return len(*h)
    }

    // Метод Less из sort.Interface
    func (h *intHeap) Less(i, j int) bool {
        // Для минимальной кучи здесь нужно заменить сравнение на <
        return (*h)[i].(int) > (*h)[j].(int)
    }

    // Метод Swap из sort.Interface
    func (h *intHeap) Swap(i, j int) {
        (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
    }

    // Top получает элемент на вершине кучи
    func (h *intHeap) Top() any {
        return (*h)[0]
    }

    /* Driver Code */
    func TestHeap(t *testing.T) {
        /* Инициализация кучи */
        // Инициализация максимальной кучи
        maxHeap := &intHeap{}
        heap.Init(maxHeap)
        /* Добавление элементов в кучу */
        // Вызываем методы heap.Interface для добавления элементов
        heap.Push(maxHeap, 1)
        heap.Push(maxHeap, 3)
        heap.Push(maxHeap, 2)
        heap.Push(maxHeap, 4)
        heap.Push(maxHeap, 5)

        /* Получение элемента на вершине кучи */
        top := maxHeap.Top()
        fmt.Printf("Элемент на вершине кучи: %d\n", top)

        /* Извлечение элемента с вершины кучи */
        // Вызываем методы heap.Interface для удаления элементов
        heap.Pop(maxHeap) // 5
        heap.Pop(maxHeap) // 4
        heap.Pop(maxHeap) // 3
        heap.Pop(maxHeap) // 2
        heap.Pop(maxHeap) // 1

        /* Получение размера кучи */
        size := len(*maxHeap)
        fmt.Printf("Число элементов в куче: %d\n", size)

        /* Проверка, пуста ли куча */
        isEmpty := len(*maxHeap) == 0
        fmt.Printf("Пуста ли куча: %t\n", isEmpty)
    }

heap.swift

    /* Инициализация кучи */
    // Тип Heap в Swift поддерживает и max-heap, и min-heap, но требует swift-collections
    var heap = Heap<Int>()

    /* Добавление элементов в кучу */
    heap.insert(1)
    heap.insert(3)
    heap.insert(2)
    heap.insert(5)
    heap.insert(4)

    /* Получение элемента на вершине кучи */
    var peek = heap.max()!

    /* Извлечение элемента с вершины кучи */
    peek = heap.removeMax() // 5
    peek = heap.removeMax() // 4
    peek = heap.removeMax() // 3
    peek = heap.removeMax() // 2
    peek = heap.removeMax() // 1

    /* Получение размера кучи */
    let size = heap.count

    /* Проверка, пуста ли куча */
    let isEmpty = heap.isEmpty

    /* Построение кучи из входного списка */
    let heap2 = Heap([1, 3, 2, 5, 4])

heap.js

    // В JavaScript нет встроенного класса Heap

heap.ts

    // В TypeScript нет встроенного класса Heap

heap.dart

    // В Dart нет встроенного класса Heap

heap.rs

    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    /* Инициализация кучи */
    // Инициализация минимальной кучи
    let mut min_heap = BinaryHeap::<Reverse<i32>>::new();
    // Инициализация максимальной кучи
    let mut max_heap = BinaryHeap::new();

    /* Добавление элементов в кучу */
    max_heap.push(1);
    max_heap.push(3);
    max_heap.push(2);
    max_heap.push(5);
    max_heap.push(4);

    /* Получение элемента на вершине кучи */
    let peek = max_heap.peek().unwrap();  // 5

    /* Извлечение элемента с вершины кучи */
    // Извлеченные элементы образуют последовательность по убыванию
    let peek = max_heap.pop().unwrap();   // 5
    let peek = max_heap.pop().unwrap();   // 4
    let peek = max_heap.pop().unwrap();   // 3
    let peek = max_heap.pop().unwrap();   // 2
    let peek = max_heap.pop().unwrap();   // 1

    /* Получение размера кучи */
    let size = max_heap.len();

    /* Проверка, пуста ли куча */
    let is_empty = max_heap.is_empty();

    /* Построение кучи из входного списка */
    let min_heap = BinaryHeap::from(vec![Reverse(1), Reverse(3), Reverse(2), Reverse(5), Reverse(4)]);

heap.c

    // В C нет встроенного класса Heap

heap.kt

    /* Инициализация кучи */
    // Инициализация минимальной кучи
    var minHeap = PriorityQueue<Int>()
    // Инициализация максимальной кучи (достаточно изменить Comparator через lambda)
    val maxHeap = PriorityQueue { a: Int, b: Int -> b - a }

    /* Добавление элементов в кучу */
    maxHeap.offer(1)
    maxHeap.offer(3)
    maxHeap.offer(2)
    maxHeap.offer(5)
    maxHeap.offer(4)

    /* Получение элемента на вершине кучи */
    var peek = maxHeap.peek() // 5

    /* Извлечение элемента с вершины кучи */
    // Извлеченные элементы образуют последовательность по убыванию
    peek = maxHeap.poll() // 5
    peek = maxHeap.poll() // 4
    peek = maxHeap.poll() // 3
    peek = maxHeap.poll() // 2
    peek = maxHeap.poll() // 1

    /* Получение размера кучи */
    val size = maxHeap.size

    /* Проверка, пуста ли куча */
    val isEmpty = maxHeap.isEmpty()

    /* Построение кучи из входного списка */
    minHeap = PriorityQueue(mutableListOf(1, 3, 2, 5, 4))

heap.rb

    # В Ruby нет встроенного класса Heap

Визуализация выполнения

https://pythontutor.com/render.html#code=import%20heapq%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%D0%98%D0%BD%D0%B8%D1%86%D0%B8%D0%B0%D0%BB%D0%B8%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D1%82%D1%8C%20min-%D0%BA%D1%83%D1%87%D1%83%0A%20%20%20%20min_heap%2C%20flag%20%3D%20%5B%5D%2C%201%0A%20%20%20%20%23%20%D0%98%D0%BD%D0%B8%D1%86%D0%B8%D0%B0%D0%BB%D0%B8%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D1%82%D1%8C%20max-%D0%BA%D1%83%D1%87%D1%83%0A%20%20%20%20max_heap%2C%20flag%20%3D%20%5B%5D%2C%20-1%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%9C%D0%BE%D0%B4%D1%83%D0%BB%D1%8C%20heapq%20%D0%B2%20Python%20%D0%BF%D0%BE%20%D1%83%D0%BC%D0%BE%D0%BB%D1%87%D0%B0%D0%BD%D0%B8%D1%8E%20%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D1%83%D0%B5%D1%82%20min-%D0%BA%D1%83%D1%87%D1%83%0A%20%20%20%20%23%20%D0%95%D1%81%D0%BB%D0%B8%20%D0%BF%D0%B5%D1%80%D0%B5%D0%B4%20%D0%BF%D0%BE%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC%20%D0%B2%20%D0%BA%D1%83%D1%87%D1%83%20%D0%B1%D1%80%D0%B0%D1%82%D1%8C%20%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D0%BD%D0%B8%D0%B5%20%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D0%B0%2C%20%D0%BC%D0%BE%D0%B6%D0%BD%D0%BE%20%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%B8%D1%82%D1%8C%20%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5%20%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0%20%D0%B8%20%D1%82%D0%B5%D0%BC%20%D1%81%D0%B0%D0%BC%D1%8B%D0%BC%20%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D1%82%D1%8C%20max-%D0%BA%D1%83%D1%87%D1%83%0A%20%20%20%20%23%20%D0%92%20%D1%8D%D1%82%D0%BE%D0%BC%20%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D0%B5%20flag%20%3D%201%20%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D1%83%D0%B5%D1%82%20min-%D0%BA%D1%83%D1%87%D0%B5%2C%20%D0%B0%20flag%20%3D%20-1%20%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D1%83%D0%B5%D1%82%20max-%D0%BA%D1%83%D1%87%D0%B5%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%94%D0%BE%D0%B1%D0%B0%D0%B2%D0%B8%D1%82%D1%8C%20%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%20%D0%B2%20%D0%BA%D1%83%D1%87%D1%83%0A%20%20%20%20heapq.heappush%28max_heap%2C%20flag%20%2A%201%29%0A%20%20%20%20heapq.heappush%28max_heap%2C%20flag%20%2A%203%29%0A%20%20%20%20heapq.heappush%28max_heap%2C%20flag%20%2A%202%29%0A%20%20%20%20heapq.heappush%28max_heap%2C%20flag%20%2A%205%29%0A%20%20%20%20heapq.heappush%28max_heap%2C%20flag%20%2A%204%29%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B8%D1%82%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B9%20%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%20%D0%BA%D1%83%D1%87%D0%B8%0A%20%20%20%20peek%20%3D%20flag%20%2A%20max_heap%5B0%5D%20%23%205%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%98%D0%B7%D0%B2%D0%BB%D0%B5%D1%87%D1%8C%20%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%B8%D0%B9%20%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%20%D0%B8%D0%B7%20%D0%BA%D1%83%D1%87%D0%B8%0A%20%20%20%20%23%20%D0%98%D0%B7%D0%B2%D0%BB%D0%B5%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5%20%D0%B8%D0%B7%20%D0%BA%D1%83%D1%87%D0%B8%20%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D1%8B%20%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D1%83%D1%8E%D1%82%20%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C%20%D0%BE%D1%82%20%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B3%D0%BE%20%D0%BA%20%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%BC%D1%83%0A%20%20%20%20val%20%3D%20flag%20%2A%20heapq.heappop%28max_heap%29%20%23%205%0A%20%20%20%20val%20%3D%20flag%20%2A%20heapq.heappop%28max_heap%29%20%23%204%0A%20%20%20%20val%20%3D%20flag%20%2A%20heapq.heappop%28max_heap%29%20%23%203%0A%20%20%20%20val%20%3D%20flag%20%2A%20heapq.heappop%28max_heap%29%20%23%202%0A%20%20%20%20val%20%3D%20flag%20%2A%20heapq.heappop%28max_heap%29%20%23%201%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B8%D1%82%D1%8C%20%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%20%D0%BA%D1%83%D1%87%D0%B8%0A%20%20%20%20size%20%3D%20len%28max_heap%29%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%82%D1%8C%2C%20%D0%BF%D1%83%D1%81%D1%82%D0%B0%20%D0%BB%D0%B8%20%D0%BA%D1%83%D1%87%D0%B0%0A%20%20%20%20is_empty%20%3D%20not%20max_heap%0A%20%20%20%20%0A%20%20%20%20%23%20%D0%92%D1%85%D0%BE%D0%B4%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA%D0%B8%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5%20%D0%BA%D1%83%D1%87%D0%B8%0A%20%20%20%20min_heap%20%3D%20%5B1%2C%203%2C%202%2C%205%2C%204%5D%0A%20%20%20%20heapq.heapify%28min_heap%29&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

## 8.1.2 Реализация кучи

Ниже реализуется максимальная куча. Чтобы преобразовать ее в минимальную кучу, достаточно инвертировать всю логику сравнений по величине, например заменить \(\geq\) на \(\leq\) . Заинтересованные читатели могут попробовать реализовать это самостоятельно.

### 1. Хранение и представление кучи

В разделе «Двоичные деревья» мы уже говорили, что полное двоичное дерево очень удобно представлять массивом. Поскольку куча как раз и является полным двоичным деревом, для хранения кучи мы также будем использовать массив.

Когда двоичное дерево представляется массивом, элементы массива соответствуют значениям узлов, а индексы - положениям этих узлов в двоичном дереве. Указатели на узлы реализуются через формулы отображения индексов.

Как показано на рисунке 8-2, для заданного индекса \(i\) индекс левого дочернего узла равен \(2i + 1\) , правого дочернего узла - \(2i + 2\) , а родительского узла - \((i - 1) / 2\) с округлением вниз. Если индекс выходит за допустимые границы, это означает пустой узел или отсутствие узла.

Рисунок 8-2 Представление и хранение кучи

Мы можем инкапсулировать формулы отображения индексов в функции, чтобы потом было удобнее ими пользоваться:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
my_heap.py

    def left(self, i: int) -> int:
        """Получить индекс левого дочернего узла"""
        return 2 * i + 1

    def right(self, i: int) -> int:
        """Получить индекс правого дочернего узла"""
        return 2 * i + 2

    def parent(self, i: int) -> int:
        """Получить индекс родительского узла"""
        return (i - 1) // 2  # Округление вниз при делении

my_heap.cpp

    /* Получить индекс левого дочернего узла */
    int left(int i) {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    int right(int i) {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    int parent(int i) {
        return (i - 1) / 2; // Округление вниз при делении
    }

my_heap.java

    /* Получить индекс левого дочернего узла */
    int left(int i) {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    int right(int i) {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    int parent(int i) {
        return (i - 1) / 2; // Округление вниз при делении
    }

my_heap.cs

    /* Получить индекс левого дочернего узла */
    int Left(int i) {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    int Right(int i) {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    int Parent(int i) {
        return (i - 1) / 2; // Округление вниз при делении
    }

my_heap.go

    /* Получить индекс левого дочернего узла */
    func (h *maxHeap) left(i int) int {
        return 2*i + 1
    }

    /* Получить индекс правого дочернего узла */
    func (h *maxHeap) right(i int) int {
        return 2*i + 2
    }

    /* Получить индекс родительского узла */
    func (h *maxHeap) parent(i int) int {
        // Округление вниз при делении
        return (i - 1) / 2
    }

my_heap.swift

    /* Получить индекс левого дочернего узла */
    func left(i: Int) -> Int {
        2 * i + 1
    }

    /* Получить индекс правого дочернего узла */
    func right(i: Int) -> Int {
        2 * i + 2
    }

    /* Получить индекс родительского узла */
    func parent(i: Int) -> Int {
        (i - 1) / 2 // Округление вниз при делении
    }

my_heap.js

    /* Получить индекс левого дочернего узла */
    #left(i) {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    #right(i) {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    #parent(i) {
        return Math.floor((i - 1) / 2); // Округление вниз при делении
    }

my_heap.ts

    /* Получить индекс левого дочернего узла */
    left(i: number): number {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    right(i: number): number {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    parent(i: number): number {
        return Math.floor((i - 1) / 2); // Округление вниз при делении
    }

my_heap.dart

    /* Получить индекс левого дочернего узла */
    int _left(int i) {
      return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    int _right(int i) {
      return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    int _parent(int i) {
      return (i - 1) ~/ 2; // Округление вниз при делении
    }

my_heap.rs

    /* Получить индекс левого дочернего узла */
    fn left(i: usize) -> usize {
        2 * i + 1
    }

    /* Получить индекс правого дочернего узла */
    fn right(i: usize) -> usize {
        2 * i + 2
    }

    /* Получить индекс родительского узла */
    fn parent(i: usize) -> usize {
        (i - 1) / 2 // Округление вниз при делении
    }

my_heap.c

    /* Получить индекс левого дочернего узла */
    int left(MaxHeap *maxHeap, int i) {
        return 2 * i + 1;
    }

    /* Получить индекс правого дочернего узла */
    int right(MaxHeap *maxHeap, int i) {
        return 2 * i + 2;
    }

    /* Получить индекс родительского узла */
    int parent(MaxHeap *maxHeap, int i) {
        return (i - 1) / 2; // Округление вниз
    }

my_heap.kt

    /* Получить индекс левого дочернего узла */
    fun left(i: Int): Int {
        return 2 * i + 1
    }

    /* Получить индекс правого дочернего узла */
    fun right(i: Int): Int {
        return 2 * i + 2
    }

    /* Получить индекс родительского узла */
    fun parent(i: Int): Int {
        return (i - 1) / 2 // Округление вниз при делении
    }

my_heap.rb

    ### Получить индекс левого дочернего узла ###
    def left(i)
      2 * i + 1
    end

    ### Получить индекс правого дочернего узла ###
    def right(i)
      2 * i + 2
    end

    ### Получить индекс родительского узла ###
    def parent(i)
      (i - 1) / 2     # Округление вниз при делении
    end

### 2. Доступ к элементу на вершине кучи

Элемент на вершине кучи - это корневой узел двоичного дерева, то есть первый элемент списка:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
my_heap.py

    def peek(self) -> int:
        """Доступ к элементу на вершине кучи"""
        return self.max_heap[0]

my_heap.cpp

    /* Доступ к элементу на вершине кучи */
    int peek() {
        return maxHeap[0];
    }

my_heap.java

    /* Доступ к элементу на вершине кучи */
    int peek() {
        return maxHeap.get(0);
    }

my_heap.cs

    /* Доступ к элементу на вершине кучи */
    int Peek() {
        return maxHeap[0];
    }

my_heap.go

    /* Доступ к элементу на вершине кучи */
    func (h *maxHeap) peek() any {
        return h.data[0]
    }

my_heap.swift

    /* Доступ к элементу на вершине кучи */
    func peek() -> Int {
        maxHeap[0]
    }

my_heap.js

    /* Доступ к элементу на вершине кучи */
    peek() {
        return this.#maxHeap[0];
    }

my_heap.ts

    /* Доступ к элементу на вершине кучи */
    peek(): number {
        return this.maxHeap[0];
    }

my_heap.dart

    /* Доступ к элементу на вершине кучи */
    int peek() {
      return _maxHeap[0];
    }

my_heap.rs

    /* Доступ к элементу на вершине кучи */
    fn peek(&self) -> Option<i32> {
        self.max_heap.first().copied()
    }

my_heap.c

    /* Доступ к элементу на вершине кучи */
    int peek(MaxHeap *maxHeap) {
        return maxHeap->data[0];
    }

my_heap.kt

    /* Доступ к элементу на вершине кучи */
    fun peek(): Int {
        return maxHeap[0]
    }

my_heap.rb

    ### Доступ к элементу на вершине кучи ###
    def peek
      @max_heap[0]
    end

Визуализация кода

Во весь экран >

### 3. Добавление элемента в кучу

Пусть дан элемент `val` . Сначала мы помещаем его в основание кучи. После добавления свойства кучи могут нарушиться, потому что `val` может оказаться больше, чем другие элементы в куче. Поэтому необходимо восстановить порядок на пути от вставленного узла к корню. Эта операция называется упорядочиванием кучи.

Рассмотрим ситуацию, когда упорядочивание выполняется снизу вверх, начиная от только что вставленного узла. Как показано на рисунке 8-3, мы сравниваем значение вставленного узла со значением его родителя. Если вставленный узел больше, то меняем их местами. Затем продолжаем выполнять ту же операцию и последовательно восстанавливать корректность всех узлов по пути снизу вверх, пока не выйдем за корень или не встретим узел, для которого обмен не требуется.

<1><2><3><4><5><6><7><8><9>

Рисунок 8-3 Шаги добавления элемента в кучу

Пусть общее число узлов равно \(n\) , тогда высота дерева равна \(O(\log n)\) . Следовательно, максимальное число итераций операции упорядочивания кучи тоже не превышает \(O(\log n)\) . Отсюда временная сложность добавления элемента в кучу равна \(O(\log n)\) . Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
my_heap.py

    def push(self, val: int):
        """Добавление элемента в кучу"""
        # Добавление узла
        self.max_heap.append(val)
        # Просеивание снизу вверх
        self.sift_up(self.size() - 1)

    def sift_up(self, i: int):
        """Начиная с узла i, выполнить просеивание снизу вверх"""
        while True:
            # Получение родительского узла для узла i
            p = self.parent(i)
            # Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if p < 0 or self.max_heap[i] <= self.max_heap[p]:
                break
            # Поменять два узла местами
            self.swap(i, p)
            # Циклическое просеивание вверх
            i = p

my_heap.cpp

    /* Добавление элемента в кучу */
    void push(int val) {
        // Добавление узла
        maxHeap.push_back(val);
        // Просеивание снизу вверх
        siftUp(size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    void siftUp(int i) {
        while (true) {
            // Получение родительского узла для узла i
            int p = parent(i);
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || maxHeap[i] <= maxHeap[p])
                break;
            // Поменять два узла местами
            swap(maxHeap[i], maxHeap[p]);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.java

    /* Добавление элемента в кучу */
    void push(int val) {
        // Добавление узла
        maxHeap.add(val);
        // Просеивание снизу вверх
        siftUp(size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    void siftUp(int i) {
        while (true) {
            // Получение родительского узла для узла i
            int p = parent(i);
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))
                break;
            // Поменять два узла местами
            swap(i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.cs

    /* Добавление элемента в кучу */
    void Push(int val) {
        // Добавление узла
        maxHeap.Add(val);
        // Просеивание снизу вверх
        SiftUp(Size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    void SiftUp(int i) {
        while (true) {
            // Получение родительского узла для узла i
            int p = Parent(i);
            // Если «выход за пределы корневого узла» или «узел не требует исправления», завершить просеивание
            if (p < 0 || maxHeap[i] <= maxHeap[p])
                break;
            // Поменять два узла местами
            Swap(i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.go

    /* Добавление элемента в кучу */
    func (h *maxHeap) push(val any) {
        // Добавление узла
        h.data = append(h.data, val)
        // Просеивание снизу вверх
        h.siftUp(len(h.data) - 1)
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    func (h *maxHeap) siftUp(i int) {
        for true {
            // Получение родительского узла для узла i
            p := h.parent(i)
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if p < 0 || h.data[i].(int) <= h.data[p].(int) {
                break
            }
            // Поменять два узла местами
            h.swap(i, p)
            // Циклическое просеивание вверх
            i = p
        }
    }

my_heap.swift

    /* Добавление элемента в кучу */
    func push(val: Int) {
        // Добавление узла
        maxHeap.append(val)
        // Просеивание снизу вверх
        siftUp(i: size() - 1)
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    func siftUp(i: Int) {
        var i = i
        while true {
            // Получение родительского узла для узла i
            let p = parent(i: i)
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if p < 0 || maxHeap[i] <= maxHeap[p] {
                break
            }
            // Поменять два узла местами
            swap(i: i, j: p)
            // Циклическое просеивание вверх
            i = p
        }
    }

my_heap.js

    /* Добавление элемента в кучу */
    push(val) {
        // Добавление узла
        this.#maxHeap.push(val);
        // Просеивание снизу вверх
        this.#siftUp(this.size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    #siftUp(i) {
        while (true) {
            // Получение родительского узла для узла i
            const p = this.#parent(i);
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || this.#maxHeap[i] <= this.#maxHeap[p]) break;
            // Поменять два узла местами
            this.#swap(i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.ts

    /* Добавление элемента в кучу */
    push(val: number): void {
        // Добавление узла
        this.maxHeap.push(val);
        // Просеивание снизу вверх
        this.siftUp(this.size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    siftUp(i: number): void {
        while (true) {
            // Получение родительского узла для узла i
            const p = this.parent(i);
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || this.maxHeap[i] <= this.maxHeap[p]) break;
            // Поменять два узла местами
            this.swap(i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.dart

    /* Добавление элемента в кучу */
    void push(int val) {
      // Добавление узла
      _maxHeap.add(val);
      // Просеивание снизу вверх
      siftUp(size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    void siftUp(int i) {
      while (true) {
        // Получение родительского узла для узла i
        int p = _parent(i);
        // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
        if (p < 0 || _maxHeap[i] <= _maxHeap[p]) {
          break;
        }
        // Поменять два узла местами
        _swap(i, p);
        // Циклическое просеивание вверх
        i = p;
      }
    }

my_heap.rs

    /* Добавление элемента в кучу */
    fn push(&mut self, val: i32) {
        // Добавление узла
        self.max_heap.push(val);
        // Просеивание снизу вверх
        self.sift_up(self.size() - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    fn sift_up(&mut self, mut i: usize) {
        loop {
            // Если узел i уже является вершиной кучи, завершить просеивание
            if i == 0 {
                break;
            }
            // Получение родительского узла для узла i
            let p = Self::parent(i);
            // Когда «узел не требует исправления», завершить просеивание
            if self.max_heap[i] <= self.max_heap[p] {
                break;
            }
            // Поменять два узла местами
            self.swap(i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.c

    /* Добавление элемента в кучу */
    void push(MaxHeap *maxHeap, int val) {
        // По умолчанию не следует добавлять так много узлов
        if (maxHeap->size == MAX_SIZE) {
            printf("heap is full!");
            return;
        }
        // Добавление узла
        maxHeap->data[maxHeap->size] = val;
        maxHeap->size++;

        // Просеивание снизу вверх
        siftUp(maxHeap, maxHeap->size - 1);
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    void siftUp(MaxHeap *maxHeap, int i) {
        while (true) {
            // Получение родительского узла для узла i
            int p = parent(maxHeap, i);
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || maxHeap->data[i] <= maxHeap->data[p]) {
                break;
            }
            // Поменять два узла местами
            swap(maxHeap, i, p);
            // Циклическое просеивание вверх
            i = p;
        }
    }

my_heap.kt

    /* Добавление элемента в кучу */
    fun push(_val: Int) {
        // Добавление узла
        maxHeap.add(_val)
        // Просеивание снизу вверх
        siftUp(size() - 1)
    }

    /* Начиная с узла i, выполнить просеивание снизу вверх */
    fun siftUp(it: Int) {
        // Параметры функций в Kotlin неизменяемы, поэтому создается временная переменная
        var i = it
        while (true) {
            // Получение родительского узла для узла i
            val p = parent(i)
            // Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
            if (p < 0 || maxHeap[i] <= maxHeap[p]) break
            // Поменять два узла местами
            swap(i, p)
            // Циклическое просеивание вверх
            i = p
        }
    }

my_heap.rb

    ### Добавление элемента в кучу ###
    def push(val)
      # Добавление узла
      @max_heap << val
      # Просеивание снизу вверх
      sift_up(size - 1)
    end

    ### Начиная с узла i, выполнить просеивание снизу вверх ###
    def sift_up(i)
      loop do
        # Получение родительского узла для узла i
        p = parent(i)
        # Завершить heapify, когда «корневой узел уже пройден» или «узел не требует исправления»
        break if p < 0 || @max_heap[i] <= @max_heap[p]
        # Поменять два узла местами
        swap(i, p)
        # Циклическое просеивание вверх
        i = p
      end
    end

Визуализация кода

Во весь экран >

### 4. Извлечение элемента с вершины кучи

Элемент на вершине кучи - это корневой узел двоичного дерева, то есть первый элемент списка. Если просто удалить первый элемент списка, то индексы всех узлов двоичного дерева изменятся, и это сильно затруднит последующее восстановление структуры при помощи упорядочивания кучи. Чтобы по возможности минимизировать изменение индексов элементов, мы используем следующий порядок действий.

1. Поменять местами элемент на вершине кучи и элемент у основания кучи, то есть поменять корневой узел с самым правым листовым узлом.
2. После обмена удалить основание кучи из списка. Стоит отметить, что, поскольку обмен уже выполнен, фактически удаляется исходный элемент вершины кучи.
3. Начиная от корневого узла, выполнить упорядочивание кучи сверху вниз.

Как показано на рисунке 8-4, направление операции упорядочивания кучи сверху вниз противоположно операции упорядочивания кучи снизу вверх. Мы сравниваем значение корневого узла со значениями двух дочерних узлов, выбираем больший дочерний узел и меняем его местами с корневым узлом. Затем циклически повторяем ту же операцию, пока не выйдем за листовой узел или не встретим узел, который уже не требует обмена.

<1><2><3><4><5><6><7><8><9><10>

Рисунок 8-4 Шаги извлечения элемента с вершины кучи

Как и операция добавления в кучу, операция извлечения элемента с вершины кучи также имеет временную сложность \(O(\log n)\) . Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
my_heap.py

    def pop(self) -> int:
        """Извлечение элемента из кучи"""
        # Обработка пустого случая
        if self.is_empty():
            raise IndexError("куча пуста")
        # Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        self.swap(0, self.size() - 1)
        # Удаление узла
        val = self.max_heap.pop()
        # Просеивание сверху вниз
        self.sift_down(0)
        # Вернуть элемент с вершины кучи
        return val

    def sift_down(self, i: int):
        """Начиная с узла i, выполнить просеивание сверху вниз"""
        while True:
            # Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            l, r, ma = self.left(i), self.right(i), i
            if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
                ma = l
            if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
                ma = r
            # Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i:
                break
            # Поменять два узла местами
            self.swap(i, ma)
            # Циклическое просеивание вниз
            i = ma

my_heap.cpp

    /* Извлечение элемента из кучи */
    void pop() {
        // Обработка пустого случая
        if (isEmpty()) {
            throw out_of_range("куча пуста");
        }
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        swap(maxHeap[0], maxHeap[size() - 1]);
        // Удаление узла
        maxHeap.pop_back();
        // Просеивание сверху вниз
        siftDown(0);
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = left(i), r = right(i), ma = i;
            if (l < size() && maxHeap[l] > maxHeap[ma])
                ma = l;
            if (r < size() && maxHeap[r] > maxHeap[ma])
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i)
                break;
            swap(maxHeap[i], maxHeap[ma]);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.java

    /* Извлечение элемента из кучи */
    int pop() {
        // Обработка пустого случая
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        swap(0, size() - 1);
        // Удаление узла
        int val = maxHeap.remove(size() - 1);
        // Просеивание сверху вниз
        siftDown(0);
        // Вернуть элемент с вершины кучи
        return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = left(i), r = right(i), ma = i;
            if (l < size() && maxHeap.get(l) > maxHeap.get(ma))
                ma = l;
            if (r < size() && maxHeap.get(r) > maxHeap.get(ma))
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i)
                break;
            // Поменять два узла местами
            swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.cs

    /* Извлечение элемента из кучи */
    int Pop() {
        // Обработка пустого случая
        if (IsEmpty())
            throw new IndexOutOfRangeException();
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        Swap(0, Size() - 1);
        // Удаление узла
        int val = maxHeap.Last();
        maxHeap.RemoveAt(Size() - 1);
        // Просеивание сверху вниз
        SiftDown(0);
        // Вернуть элемент с вершины кучи
        return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    void SiftDown(int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = Left(i), r = Right(i), ma = i;
            if (l < Size() && maxHeap[l] > maxHeap[ma])
                ma = l;
            if (r < Size() && maxHeap[r] > maxHeap[ma])
                ma = r;
            // Если «узел i максимален» или «выход за пределы листовых узлов», завершить просеивание
            if (ma == i) break;
            // Поменять два узла местами
            Swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.go

    /* Извлечение элемента из кучи */
    func (h *maxHeap) pop() any {
        // Обработка пустого случая
        if h.isEmpty() {
            fmt.Println("error")
            return nil
        }
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        h.swap(0, h.size()-1)
        // Удаление узла
        val := h.data[len(h.data)-1]
        h.data = h.data[:len(h.data)-1]
        // Просеивание сверху вниз
        h.siftDown(0)

        // Вернуть элемент с вершины кучи
        return val
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    func (h *maxHeap) siftDown(i int) {
        for true {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как max
            l, r, max := h.left(i), h.right(i), i
            if l < h.size() && h.data[l].(int) > h.data[max].(int) {
                max = l
            }
            if r < h.size() && h.data[r].(int) > h.data[max].(int) {
                max = r
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if max == i {
                break
            }
            // Поменять два узла местами
            h.swap(i, max)
            // Циклическое просеивание вниз
            i = max
        }
    }

my_heap.swift

    /* Извлечение элемента из кучи */
    func pop() -> Int {
        // Обработка пустого случая
        if isEmpty() {
            fatalError("куча пуста")
        }
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        swap(i: 0, j: size() - 1)
        // Удаление узла
        let val = maxHeap.remove(at: size() - 1)
        // Просеивание сверху вниз
        siftDown(i: 0)
        // Вернуть элемент с вершины кучи
        return val
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    func siftDown(i: Int) {
        var i = i
        while true {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let l = left(i: i)
            let r = right(i: i)
            var ma = i
            if l < size(), maxHeap[l] > maxHeap[ma] {
                ma = l
            }
            if r < size(), maxHeap[r] > maxHeap[ma] {
                ma = r
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i {
                break
            }
            // Поменять два узла местами
            swap(i: i, j: ma)
            // Циклическое просеивание вниз
            i = ma
        }
    }

my_heap.js

    /* Извлечение элемента из кучи */
    pop() {
        // Обработка пустого случая
        if (this.isEmpty()) throw new Error('куча пуста');
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        this.#swap(0, this.size() - 1);
        // Удаление узла
        const val = this.#maxHeap.pop();
        // Просеивание сверху вниз
        this.#siftDown(0);
        // Вернуть элемент с вершины кучи
        return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    #siftDown(i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            const l = this.#left(i),
                r = this.#right(i);
            let ma = i;
            if (l < this.size() && this.#maxHeap[l] > this.#maxHeap[ma]) ma = l;
            if (r < this.size() && this.#maxHeap[r] > this.#maxHeap[ma]) ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma === i) break;
            // Поменять два узла местами
            this.#swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.ts

    /* Извлечение элемента из кучи */
    pop(): number {
        // Обработка пустого случая
        if (this.isEmpty()) throw new RangeError('Heap is empty.');
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        this.swap(0, this.size() - 1);
        // Удаление узла
        const val = this.maxHeap.pop();
        // Просеивание сверху вниз
        this.siftDown(0);
        // Вернуть элемент с вершины кучи
        return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    siftDown(i: number): void {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            const l = this.left(i),
                r = this.right(i);
            let ma = i;
            if (l < this.size() && this.maxHeap[l] > this.maxHeap[ma]) ma = l;
            if (r < this.size() && this.maxHeap[r] > this.maxHeap[ma]) ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma === i) break;
            // Поменять два узла местами
            this.swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.dart

    /* Извлечение элемента из кучи */
    int pop() {
      // Обработка пустого случая
      if (isEmpty()) throw Exception('куча пуста');
      // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
      _swap(0, size() - 1);
      // Удаление узла
      int val = _maxHeap.removeLast();
      // Просеивание сверху вниз
      siftDown(0);
      // Вернуть элемент с вершины кучи
      return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(int i) {
      while (true) {
        // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
        int l = _left(i);
        int r = _right(i);
        int ma = i;
        if (l < size() && _maxHeap[l] > _maxHeap[ma]) ma = l;
        if (r < size() && _maxHeap[r] > _maxHeap[ma]) ma = r;
        // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
        if (ma == i) break;
        // Поменять два узла местами
        _swap(i, ma);
        // Циклическое просеивание вниз
        i = ma;
      }
    }

my_heap.rs

    /* Извлечение элемента из кучи */
    fn pop(&mut self) -> i32 {
        // Обработка пустого случая
        if self.is_empty() {
            panic!("index out of bounds");
        }
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        self.swap(0, self.size() - 1);
        // Удаление узла
        let val = self.max_heap.pop().unwrap();
        // Просеивание сверху вниз
        self.sift_down(0);
        // Вернуть элемент с вершины кучи
        val
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    fn sift_down(&mut self, mut i: usize) {
        loop {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let (l, r, mut ma) = (Self::left(i), Self::right(i), i);
            if l < self.size() && self.max_heap[l] > self.max_heap[ma] {
                ma = l;
            }
            if r < self.size() && self.max_heap[r] > self.max_heap[ma] {
                ma = r;
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i {
                break;
            }
            // Поменять два узла местами
            self.swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

my_heap.c

    /* Извлечение элемента из кучи */
    int pop(MaxHeap *maxHeap) {
        // Обработка пустого случая
        if (isEmpty(maxHeap)) {
            printf("heap is empty!");
            return INT_MAX;
        }
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        swap(maxHeap, 0, size(maxHeap) - 1);
        // Удаление узла
        int val = maxHeap->data[maxHeap->size - 1];
        maxHeap->size--;
        // Просеивание сверху вниз
        siftDown(maxHeap, 0);

        // Вернуть элемент с вершины кучи
        return val;
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(MaxHeap *maxHeap, int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как max
            int l = left(maxHeap, i);
            int r = right(maxHeap, i);
            int max = i;
            if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[max]) {
                max = l;
            }
            if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[max]) {
                max = r;
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (max == i) {
                break;
            }
            // Поменять два узла местами
            swap(maxHeap, i, max);
            // Циклическое просеивание вниз
            i = max;
        }
    }

my_heap.kt

    /* Извлечение элемента из кучи */
    fun pop(): Int {
        // Обработка пустого случая
        if (isEmpty()) throw IndexOutOfBoundsException()
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        swap(0, size() - 1)
        // Удаление узла
        val _val = maxHeap.removeAt(size() - 1)
        // Просеивание сверху вниз
        siftDown(0)
        // Вернуть элемент с вершины кучи
        return _val
    }

    /* Начиная с узла i, выполнить просеивание сверху вниз */
    fun siftDown(it: Int) {
        // Параметры функций в Kotlin неизменяемы, поэтому создается временная переменная
        var i = it
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            val l = left(i)
            val r = right(i)
            var ma = i
            if (l < size() && maxHeap[l] > maxHeap[ma]) ma = l
            if (r < size() && maxHeap[r] > maxHeap[ma]) ma = r
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i) break
            // Поменять два узла местами
            swap(i, ma)
            // Циклическое просеивание вниз
            i = ma
        }
    }

my_heap.rb

    ### Извлечение элемента из кучи ###
    def pop
      # Обработка пустого случая
      raise IndexError, "куча пуста" if is_empty?
      # Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
      swap(0, size - 1)
      # Удаление узла
      val = @max_heap.pop
      # Просеивание сверху вниз
      sift_down(0)
      # Вернуть элемент с вершины кучи
      val
    end

    ### Начиная с узла i, выполнить просеивание сверху вниз ###
    def sift_down(i)
      loop do
        # Определить узел с максимальным значением среди i, l и r и обозначить его как ma
        l, r, ma = left(i), right(i), i
        ma = l if l < size && @max_heap[l] > @max_heap[ma]
        ma = r if r < size && @max_heap[r] > @max_heap[ma]

        # Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
        break if ma == i

        # Поменять два узла местами
        swap(i, ma)
        # Циклическое просеивание вниз
        i = ma
      end
    end

Визуализация кода

Во весь экран >

## 8.1.3 Типичные применения кучи

- Очередь с приоритетом: куча обычно является предпочтительной структурой данных для реализации очереди с приоритетом. Добавление и извлечение элементов имеют временную сложность \(O(\log n)\) , а построение кучи - \(O(n)\) , и все эти операции выполняются очень эффективно.
- Пирамидальная сортировка: для заданного набора данных можно построить кучу, а затем непрерывно извлекать из нее элементы, получая отсортированные данные. Однако на практике мы обычно используем более изящную реализацию пирамидальной сортировки. Подробности см. в разделе «Пирамидальная сортировка».
- Получение наибольших \(k\) элементов: это классическая алгоритмическая задача и одновременно типичное применение кучи. Например, выбор 10 самых горячих новостей для списка популярных тем или выбор 10 самых продаваемых товаров.

##### Оставляйте свои идеи, вопросы и предложения в комментариях