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

# 8.2 Построение кучи

В некоторых случаях требуется построить кучу, используя сразу все элементы списка. Этот процесс называется построением кучи.

## 8.2.1 Реализация через операцию добавления в кучу

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

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

Пусть число элементов равно \(n\). Так как каждая операция добавления требует \(O(\log{n})\) времени, временная сложность такого построения кучи составляет \(O(n \log n)\) .

## 8.2.2 Реализация через обход и упорядочивание

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

1. Без изменений добавить все элементы списка в кучу. В этот момент свойства кучи еще не выполняются.
2. Обойти кучу в обратном порядке, то есть в порядке, обратном обходу по уровням, и по очереди выполнить упорядочивание сверху вниз для каждого нелистового узла.

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

Причина выбора обратного обхода в том, что он гарантирует: поддеревья ниже текущего узла уже являются корректными подкучами, а значит, упорядочивание текущего узла действительно будет эффективным.

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

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

    def __init__(self, nums: list[int]):
        """Конструктор, строящий кучу по входному списку"""
        # Добавить элементы списка в кучу без изменений
        self.max_heap = nums
        # Выполнить heapify для всех узлов, кроме листовых
        for i in range(self.parent(self.size() - 1), -1, -1):
            self.sift_down(i)

my_heap.cpp

    /* Конструктор, строящий кучу по входному списку */
    MaxHeap(vector<int> nums) {
        // Добавить элементы списка в кучу без изменений
        maxHeap = nums;
        // Выполнить heapify для всех узлов, кроме листовых
        for (int i = parent(size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

my_heap.java

    /* Конструктор, строящий кучу по входному списку */
    MaxHeap(List<Integer> nums) {
        // Добавить элементы списка в кучу без изменений
        maxHeap = new ArrayList<>(nums);
        // Выполнить heapify для всех узлов, кроме листовых
        for (int i = parent(size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

my_heap.cs

    /* Конструктор: построить кучу по входному списку */
    MaxHeap(IEnumerable<int> nums) {
        // Добавить элементы списка в кучу без изменений
        maxHeap = new List<int>(nums);
        // Выполнить heapify для всех узлов, кроме листовых
        var size = Parent(this.Size() - 1);
        for (int i = size; i >= 0; i--) {
            SiftDown(i);
        }
    }

my_heap.go

    /* Конструктор, строящий кучу по срезу */
    func newMaxHeap(nums []any) *maxHeap {
        // Добавить элементы списка в кучу без изменений
        h := &maxHeap{data: nums}
        for i := h.parent(len(h.data) - 1); i >= 0; i-- {
            // Выполнить heapify для всех узлов, кроме листовых
            h.siftDown(i)
        }
        return h
    }

my_heap.swift

    /* Конструктор, строящий кучу по входному списку */
    init(nums: [Int]) {
        // Добавить элементы списка в кучу без изменений
        maxHeap = nums
        // Выполнить heapify для всех узлов, кроме листовых
        for i in (0 ... parent(i: size() - 1)).reversed() {
            siftDown(i: i)
        }
    }

my_heap.js

    /* Конструктор, создающий пустую кучу или строящий кучу по входному списку */
    constructor(nums) {
        // Добавить элементы списка в кучу без изменений
        this.#maxHeap = nums === undefined ? [] : [...nums];
        // Выполнить heapify для всех узлов, кроме листовых
        for (let i = this.#parent(this.size() - 1); i >= 0; i--) {
            this.#siftDown(i);
        }
    }

my_heap.ts

    /* Конструктор, создающий пустую кучу или строящий кучу по входному списку */
    constructor(nums?: number[]) {
        // Добавить элементы списка в кучу без изменений
        this.maxHeap = nums === undefined ? [] : [...nums];
        // Выполнить heapify для всех узлов, кроме листовых
        for (let i = this.parent(this.size() - 1); i >= 0; i--) {
            this.siftDown(i);
        }
    }

my_heap.dart

    /* Конструктор, строящий кучу по входному списку */
    MaxHeap(List<int> nums) {
      // Добавить элементы списка в кучу без изменений
      _maxHeap = nums;
      // Выполнить heapify для всех узлов, кроме листовых
      for (int i = _parent(size() - 1); i >= 0; i--) {
        siftDown(i);
      }
    }

my_heap.rs

    /* Конструктор, строящий кучу по входному списку */
    fn new(nums: Vec<i32>) -> Self {
        // Добавить элементы списка в кучу без изменений
        let mut heap = MaxHeap { max_heap: nums };
        // Выполнить heapify для всех узлов, кроме листовых
        for i in (0..=Self::parent(heap.size() - 1)).rev() {
            heap.sift_down(i);
        }
        heap
    }

my_heap.c

    /* Конструктор, строящий кучу по срезу */
    MaxHeap *newMaxHeap(int nums[], int size) {
        // Поместить все элементы в кучу
        MaxHeap *maxHeap = (MaxHeap *)malloc(sizeof(MaxHeap));
        maxHeap->size = size;
        memcpy(maxHeap->data, nums, size * sizeof(int));
        for (int i = parent(maxHeap, size - 1); i >= 0; i--) {
            // Выполнить heapify для всех узлов, кроме листовых
            siftDown(maxHeap, i);
        }
        return maxHeap;
    }

my_heap.kt

    /* Максимальная куча */
    class MaxHeap(nums: MutableList<Int>?) {
        // Использовать список вместо массива, чтобы не учитывать проблему расширения
        private val maxHeap = mutableListOf<Int>()

        /* Конструктор, строящий кучу по входному списку */
        init {
            // Добавить элементы списка в кучу без изменений
            maxHeap.addAll(nums!!)
            // Выполнить heapify для всех узлов, кроме листовых
            for (i in parent(size() - 1) downTo 0) {
                siftDown(i)
            }
        }

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

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

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

        /* Поменять элементы местами */
        private fun swap(i: Int, j: Int) {
            val temp = maxHeap[i]
            maxHeap[i] = maxHeap[j]
            maxHeap[j] = temp
        }

        /* Получение размера кучи */
        fun size(): Int {
            return maxHeap.size
        }

        /* Проверка, пуста ли куча */
        fun isEmpty(): Boolean {
            /* Проверка, пуста ли куча */
            return size() == 0
        }

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

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

        /* Начиная с узла i, выполнить просеивание снизу вверх */
        private 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
            }
        }

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

        /* Начиная с узла i, выполнить просеивание сверху вниз */
        private 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
            }
        }

        /* Вывести кучу (двоичное дерево) */
        fun print() {
            val queue = PriorityQueue { a: Int, b: Int -> b - a }
            queue.addAll(maxHeap)
            printHeap(queue)
        }
    }

my_heap.rb

    ### Конструктор, строящий кучу по входному списку ###
    def initialize(nums)
      # Добавить элементы списка в кучу без изменений
      @max_heap = nums
      # Выполнить heapify для всех узлов, кроме листовых
      parent(size - 1).downto(0) do |i|
        sift_down(i)
      end
    end

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

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

## 8.2.3 Анализ сложности

Теперь попробуем оценить временную сложность второго способа построения кучи.

- Пусть число узлов полного двоичного дерева равно \(n\) , тогда число листовых узлов равно \((n + 1) / 2\) , где \(/\) означает целочисленное деление вниз. Следовательно, число узлов, которые нужно упорядочивать, равно \(n / 2\) .
- В процессе упорядочивания сверху вниз каждый узел в худшем случае может просеяться до листа, поэтому максимальное число итераций равно высоте двоичного дерева \(\log n\) .

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

Далее выполним более точный расчет. Чтобы упростить вычисления, предположим, что дано «идеальное двоичное дерево» высоты \(h\) с числом узлов \(n\). Это предположение не повлияет на корректность результата.

Рисунок 8-5 Число узлов на каждом уровне идеального двоичного дерева

Как показано на рисунке 8-5, максимальное число итераций упорядочивания сверху вниз для некоторого узла равно расстоянию от этого узла до листового узла, а это расстояние как раз и есть высота узла. Поэтому мы можем просуммировать для каждого уровня выражение «число узлов \(\times\) высота узла» и получить суммарное число итераций упорядочивания для всех узлов.

\[ T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{(h-1)}\times1 \]

Чтобы упростить это выражение, воспользуемся школьными знаниями о последовательностях и сначала умножим \(T(h)\) на \(2\) :

\[ \begin{aligned} T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{h-1}\times1 \newline 2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \dots + 2^{h}\times1 \newline \end{aligned} \]

Используя метод вычитания со сдвигом, вычтем из нижней строки \(2 T(h)\) верхнюю строку \(T(h)\) , тогда получим:

\[ 2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \dots + 2^{h-1} + 2^h \]

Из этого выражения видно, что \(T(h)\) представляет собой геометрическую прогрессию, поэтому можно напрямую применить формулу суммы и получить временную сложность:

\[ \begin{aligned} T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline & = 2^{h+1} - h - 2 \newline & = O(2^h) \end{aligned} \]

Далее, число узлов идеального двоичного дерева высоты \(h\) равно \(n = 2^{h+1} - 1\) , поэтому несложно получить сложность \(O(2^h) = O(n)\) . Из этого вывода следует, что построение кучи из входного списка имеет временную сложность \(O(n)\) , то есть выполняется очень эффективно.

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