Перейти к содержанию

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

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

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

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

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

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

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

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

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

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

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

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

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 - 1) / 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)\) , что очень эффективно.

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