Двоичная куча (Пирамида), Очередь с приоритетами и HeapSort

Двоичная куча: представление в массиве, процедуры sift_up и sift_down (heapify), построение кучи Build-Heap за линейное время O(N), операции Extract-Max и Increase-Key, пирамидальная сортировка HeapSort.

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Кучи: предварительные знания, план уроков и практика →

Устройство двоичной кучи в массиве

Для узла с индексом $i$ (0-indexed):

Родитель: parent(i) = (i - 1) / 2

Левый потомок: left(i) = 2 * i + 1

Правый потомок: right(i) = 2 * i + 2

Основное свойство Max-Heap:

A[\text{parent}(i)] \ge A[i]

Почему Build-Max-Heap работает за $O(N)$ ?

cpp

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }
}

Суммируя высоту узлов на каждом уровне:

\sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) = O\left( n \sum_{h=0}^{\infty} \frac{h}{2^h} \right) = O(2n) = O(N)

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».

Двоичная куча (Пирамида), Очередь с приоритетами и HeapSort

Устройство двоичной кучи в массиве

Основное свойство Max-Heap:

Почему Build-Max-Heap работает за O(N)O(N)O(N)?

Что дальше?

Почему Build-Max-Heap работает за $O(N)$ ?