7. Двоичная куча

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

Можно попытаться сделать это с помощью динамического массива или списка. Тогда мы сможем добавлять и удалять элементы за $O(1)$ (чтобы быстро удалить элемент из массива, поменяем его местами с последним элементом, после чего уменьшим длину массива на один). Однако быстро находить минимум не получится: можно пытаться поддерживать указатель на минимальный элемент, но после каждого удаления минимума новый минимум получится найти лишь перебором всех оставшихся элементов за $\Theta(n)$ (где $n$ - число элементов в множестве). Можно было бы поддерживать массив в отсортированном порядке (тогда минимум всегда будет в начале), но тогда не получится быстро добавлять или удалять произвольный элемент.

Двоичная куча (пирамида), binary heap - структура данных, которая позволяет добавлять и удалять элементы за $O(\log n)$, а также в любой момент иметь доступ к минимальному элементу в множестве за $O(1)$.

Определение

Двоичная куча из $n$ элементов - это массив $a$ с индексами от 1 до $n$, образующий двоичное дерево: для любого $1 < i \leqslant n$ родитель $i$-го элемента - это элемент с номером $\left\lfloor\frac{i}{2}\right\rfloor ;$ соответственно, для любого $1 \leqslant i \leqslant n$ дети $i$-го элемента имеют номера $2 i, 2 i+1$ (если элементы с такими номерами существуют).

При этом выполняется свойство кучи: значение любого элемента не меньше значения его родителя: $a[i] \geqslant a\left[\left\lfloor\frac{i}{2}\right]\right]$. Такую кучу также могут называть неубывающая пирамида. Аналогично, если $a[i] \leqslant a\left[\left\lfloor\frac{i}{2}\right]\right]$ - то невозрастающая пирамида.

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

Будем пользоваться терминами из теории графов. Элементы дерева (кучи) будем называть вершинами. Корень дерева - единственная вершина без родителя (в нашем случае это $a[1]$ ). Потомки вершины - это она сама, её дети, а также все их потомки; у листа (вершины без детей) потомков (кроме него самого) нет. Предок вершины $v$ - любая такая вершина $u$, что $v$ - потомок $u$. Поддерево вершины $v$ состоит из всех её потомков; $v$ - корень своего поддерева.

Иногда мы будем называть кучей не массив с индексами от 1 до $n$, а просто дерево, в котором свойство кучи выполняется для всех пар родитель-ребёнок. В этом смысле любое поддерево кучи тоже является кучей.

Глубина $x$ - количество вершин на пути от корня дерева до $x$ (все вершины являются потомками корня). Высота вершины $x$ - максимальное количество вершин на пути от $x$ до какого-либо её потомка. Высота дерева - максимум из высот вершин, то есть высота корня.

Глубина $i$-й вершины равна $\lfloor\log i\rfloor+1$, так как $i$ нужно поделить на два нацело $\lfloor\log i\rfloor$ раз, чтобы получить 1.

Высота корня - это максимум из глубин всех его потомков. Максимальная глубина у $n$-й вершины $-\lfloor\log n\rfloor+1$. Значит, высота кучи из $n$ элементов равна $\lfloor\log n\rfloor+1$.

Базовые операции

Научимся выполнять три простых операции: getMin() - поиск минимального элемента в куче, insert(x) - добавление нового элемента $x$ в кучу, и extractMin() - удаление минимума из кучи. Последние две операции будут пользоваться вспомогательными операциями $\operatorname{siftUp(i)~и~siftDown(i).~}$

Поиск минимума

Из определения кучи сразу же следует, что минимальный элемент всегда будет находиться в корне. Тогда просто вернём $a[1]$, время работы $-O(1)$.

1
2


getMin():
    return a[1]

Добавление нового элемента

Пусть свойство кучи “практически” выполняется: для некоторого $i$ известно, что $a[i]=x$ можно увеличить так, что массив $a$ станет кучей. Такую почти кучу можно “починить”, не меняя множество лежащих в ней значений, следующим образом: просто будем “поднимать” $x$ вверх, пока $x$ меньше значения в родителе.

1
2
3
4


siftUp(i):
    while i > 1 and a[i] < a[i / 2]:
        swap(a[i], a[i / 2])
        i /= 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def sift_up(arr, i):
    """
    Функция для просеивания элемента вверх в куче
    arr - массив, представляющий кучу
    i - индекс элемента для просеивания (в нотации с 0)
    """
    while i > 0:
        parent = (i - 1) // 2
        if arr[i] < arr[parent]:
            arr[i], arr[parent] = arr[parent], arr[i]
            i = parent
        else:
            break

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


#include <vector>
#include <algorithm>

void siftUp(std::vector<int>& arr, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (arr[i] < arr[parent]) {
            std::swap(arr[i], arr[parent]);
            i = parent;
        } else {
            break;
        }
    }
}

Свойства

Пусть известно, что $a[i]=x$ можно увеличить так, что массив $a$ станет кучей. Тогда после выполнения $\operatorname{siftUp}(i)$ массив $a$ станет кучей.

Доказательство

Докажем утверждение индукцией по $i$. База. Если $i=1$, то $a$ уже является кучей (если корень можно увеличить так, что он станет не больше детей, то он и сейчас не больше детей). siftUp(1) не меняет массив $a$.

Переход. Заметим сначала, что если $a$ уже является кучей, то $\operatorname{siftUp}(i)$ ничего не сделает, поэтому утверждение предложения верно.

Если $a$ не является кучей, то единственная пара родитель-ребёнок, для которой не выполняется свойство кучи - это $x=a[i] < a\left[\left\lfloor\frac{i}{2}\right\rfloor\right]=y$ (поскольку для пары, в которой $a[i]$ является родителем, увеличение $a[i]$ может лишь начать нарушать неравенство). Тогда $a$ точно станет кучей, если увеличить значение $a[i]$ до $y$.

После первой итерации цикла $x$ и $y$ поменяются местами: $y=a[i] > a\left[\left\lfloor\frac{i}{2}\right\rfloor\right]=x$. Заметим, что такой массив $a$ станет кучей, если значение $a\left[\left\lfloor\frac{i}{2}\right\rfloor\right]$ увеличить до $y$ (это равносильно увеличению $a[i]$ до $y$ в исходном массиве). Тогда, поскольку последующие действия siftUp эквивалентны рекурсивному вызову $\operatorname{siftUp}(i / 2)$, по индукции верно, что по завершении операции массив $a$ станет кучей.

Количество итераций цикла в siftUp(i) не превосходит глубины $i$-й вершины, то есть время работы оценивается как $O(\log i+1)$.

Чтобы добавить новый элемент $x$ в кучу размера $n$, запишем $x$ в $a[n+1]$ (мы предполагаем, что массив $a$ достаточно большого размера либо динамический). При этом $a$ мог перестать быть кучей, но $a[n+1]$ можно увеличить так, что $a$ снова станет кучей (например, сделав его больше всех остальных элементов), поэтому достаточно запустить от него siftUp. Получаем время работы $O(\log n)$.

1
2
3
4


insert(x):
    sz += 1 # sz - размер кучи
    a[sz] = x
    siftUp(sz)

Удаление минимума

Пусть известно, что $a[i]=x$ можно уменьшить так, что массив $a$ станет кучей. Такую почти кучу тоже можно “починить”: будем “опускать” $x$ вниз, пока $x$ больше хотя бы одного из значений в детях, при этом будем менять $x$ местами с тем ребёнком, значение в котором меньше.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


siftDown(i):
    while 2 * i <= sz:
        j = 2 * i
        if 2 * i + 1 <= sz and a[2 * i + 1] < a[2 * i]:
            j = 2 * i + 1
        # j - номер минимального по значению ребёнка i-й вершины
        if a[j] >= a[i]:
            break
        swap(a[j], a[i])
        i = j

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


def siftDown(arr, i, sz):
    """
    arr: массив
    i: индекс текущего элемента (индексация с 0)
    sz: размер кучи (не включая индекс sz)
    """
    while 2 * i + 1 < sz:  # пока есть левый ребенок
        j = 2 * i + 1  # левый ребенок
        
        # если есть правый ребенок и он меньше левого
        if 2 * i + 2 < sz and arr[2 * i + 2] < arr[2 * i + 1]:
            j = 2 * i + 2  # правый ребенок
        
        # j - индекс минимального ребенка i-го элемента
        if arr[j] >= arr[i]:
            break
        
        arr[i], arr[j] = arr[j], arr[i]
        i = j

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <vector>
#include <algorithm>

void siftDown(std::vector<int>& arr, int i, int sz) {
    // i: индекс текущего элемента (индексация с 0)
    // sz: размер кучи (не включая индекс sz)
    
    while (2 * i + 1 < sz) {  // пока есть левый ребенок
        int j = 2 * i + 1;  // левый ребенок
        
        // если есть правый ребенок и он меньше левого
        if (2 * i + 2 < sz && arr[2 * i + 2] < arr[2 * i + 1]) {
            j = 2 * i + 2;  // правый ребенок
        }
        
        // j - индекс минимального ребенка i-го элемента
        if (arr[j] >= arr[i]) {
            break;
        }
        
        std::swap(arr[i], arr[j]);
        i = j;
    }
}

Свойства

Пусть известно, что $a[i]=x$ можно уменьшить так, что массив $a$ размера $n$ станет кучей. Тогда после выполнения siftDown(i) массив $a$ станет кучей.

Доказательство

Докажем утверждение “обратной” индукцией по $i$. База. Если $i>2 n$, то $a$ уже является кучей (если лист можно уменьшить так, что он станет не меньше родителя, то он и сейчас не меньше родителя). siftDown(i) в таком случае не поменяет массив $a$.

Переход. Заметим сначала, что если $a$ уже является кучей, то siftDown(i) ничего не сделает, поэтому утверждение предложения верно.

Если $a$ не является кучей, то свойство кучи может не выполняться только для тех пар родитель-ребёнок, в которых $a[i]$ является родителем. Пусть $j$ - номер минимального по значению из детей $i$-й вершины, $y=a[j] < x$. Тогда $a$ точно станет кучей, если уменьшить значение $a[i]$ до $y$.

После первой итерации цикла $x$ и $y$ поменяются местами: $y=a[i] < a[j] = x$. Заметим, что такой массив $a$ станет кучей, если значение $a[j]$ уменьшить до $y$ (это равносильно уменьшению $a[i]$ до $y$ в исходном массиве). Тогда, поскольку последующие действия siftDown эквивалентны рекурсивному вызову $\operatorname{siftDown(j)}$, по индукции верно, что по завершении операции массив $a$ станет кучей.

Количество итераций цикла в $\operatorname{siftDown(i)}$ не больше высоты $i$-й вершины, поэтому время работы оценивается как $O(\log n-\log i+1)=O\left(\log \frac{n}{i}+1\right)$, или, более грубо, $O(\log n)$.

Чтобы удалить минимум из кучи размера $n$, поменяем местами $a[1]$ и $a[n]$, и уменьшим размер кучи на один. Теперь в $a[1]$ находится возможно не минимальный элемент, но его можно уменьшить так, что $a$ опять станет кучей (например, сделать его меньше всех остальных элементов). Тогда достаточно запустить $\operatorname{siftDown(1)}$. Получаем время работы $O(\log n)$.

1
2
3
4
5


extractMin():
    swap(a[1], a[sz])
    sz -= 1
    if sz >= 1: # если куча непуста
        siftDown(1)

1
2
3
4
5
6
7
8
9


def extractMin(arr, sz):
    # Меняем местами корень (минимальный элемент) с последним элементом
    arr[0], arr[sz-1] = arr[sz-1], arr[0]
    sz -= 1
    
    if sz >= 1:  # если куча непуста
        siftDown(arr, 0, sz)
    
    return arr, sz

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


void siftDown(std::vector<int>& arr, int i, int sz) {
    // Функция для восстановления свойства кучи
    // i - индекс элемента, который нужно просеять вниз
    // sz - текущий размер кучи
    
    while (true) {
        int left = 2 * i + 1;  // левый потомок (с учетом индексации с 0)
        int right = 2 * i + 2;  // правый потомок
        int smallest = i;
        
        if (left < sz && arr[left] < arr[smallest]) {
            smallest = left;
        }
        
        if (right < sz && arr[right] < arr[smallest]) {
            smallest = right;
        }
        
        if (smallest == i) {
            break;
        }
        
        std::swap(arr[i], arr[smallest]);
        i = smallest;
    }
}

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

Самый простой способ построить кучу из $n$ элементов - начать с пустой кучи, и добавлять элементы по одному. В худшем случае (если все вызовы $\operatorname{siftUp}$ будут подниматься до корня, то есть если элементы добавляются в убывающем порядке) получим время работы $\Theta(n \log n)$.

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

1
2
3
4


build(a, n):
    sz = n
    for i = (n / 2)..1:
        siftDown(i)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class Heap:
    def __init__(self, arr):
        self.heap = arr
        self.sz = len(arr)
    
    def build(self):
        """Построение кучи из массива"""
        self.sz = len(self.heap)
        # Начинаем с последнего родителя (n//2 - 1 в 0-индексации)
        for i in range(self.sz // 2 - 1, -1, -1):
            self._sift_down(i)
        # Дополнительный просеивание корня (для надежности)
        if self.sz > 0:
            self._sift_down(0)
    
    def _sift_down(self, i):
        """Просеивание элемента вниз"""
        largest = i
        left = 2 * i + 1  # Левый потомок
        right = 2 * i + 2  # Правый потомок
        
        # Сравниваем с левым потомком
        if left < self.sz and self.heap[left] > self.heap[largest]:
            largest = left
        
        # Сравниваем с правым потомком
        if right < self.sz and self.heap[right] > self.heap[largest]:
            largest = right
        
        # Если нужно, меняем местами и продолжаем просеивание
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._sift_down(largest)
    
    def get_heap(self):
        return self.heap

# Пример использования
def build_heap(arr, n):
    heap = Heap(arr)
    heap.build()
    return heap.get_heap()

# Тестирование
arr = [4, 10, 3, 5, 1, 8, 7]
result = build_heap(arr, len(arr))
print("Построенная куча:", result)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#include <iostream>
#include <vector>
#include <algorithm>

class Heap {
private:
    std::vector<int> heap;
    int sz;
    
    void siftDown(int i) {
        int largest = i;
        int left = 2 * i + 1;   // Левый потомок (с учетом 0-индексации)
        int right = 2 * i + 2;  // Правый потомок
        
        // Сравниваем с левым потомком
        if (left < sz && heap[left] > heap[largest]) {
            largest = left;
        }
        
        // Сравниваем с правым потомком
        if (right < sz && heap[right] > heap[largest]) {
            largest = right;
        }
        
        // Если нужно, меняем местами и продолжаем просеивание
        if (largest != i) {
            std::swap(heap[i], heap[largest]);
            siftDown(largest);
        }
    }
    
public:
    Heap(const std::vector<int>& arr) : heap(arr), sz(arr.size()) {}
    
    void build() {
        sz = heap.size();
        // Начинаем с последнего родителя (n/2 - 1 в 0-индексации)
        for (int i = sz / 2 - 1; i >= 0; i--) {
            siftDown(i);
        }
        // Дополнительное просеивание корня (для надежности)
        if (sz > 0) {
            siftDown(0);
        }
    }
    
    std::vector<int> getHeap() const {
        return heap;
    }
};

// Функция для построения кучи (интерфейс как в псевдокоде)
std::vector<int> buildHeap(std::vector<int>& arr, int n) {
    Heap heap(arr);
    heap.build();
    return heap.getHeap();
}

int main() {
    std::vector<int> arr = {4, 10, 3, 5, 1, 8, 7};
    int n = arr.size();
    
    std::vector<int> result = buildHeap(arr, n);
    
    std::cout << "Построенная куча: ";
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Лемма

После выполнения $\operatorname{build}$ массив $a$ станет кучей.

Доказательство

Докажем “обратной” индукцией по $i$, что после запуска $\operatorname{siftDown(i)}$ поддерево $i$-й вершины является кучей.

База. $i>\left\lfloor\frac{n}{2}\right\rfloor$ (на самом деле для таких $i$ мы не вызываем $\operatorname{siftDown}$, потому что он всё равно ничего не сделает). В этом случае поддерево состоит из одной вершины, поэтому утверждение верно.

Переход. По предположению индукции, поддеревья детей $i$-й вершины являются кучами. Значит, $a[i]$ можно уменьшить так, что и поддерево $i$-й вершины станет кучей (например, сделав $a[i]$ меньше значений в детях). Тогда после запуска $\operatorname{siftDown(i)}$ поддерево $i$-й вершины станет кучей.

Время работы $\operatorname{build}$ тоже складывается из $O(n)$ запусков функций, каждая из который работает за $O(\log n)$. Однако оценка времени работы $O(n \log n)$ в этом случае не является точной.

Теорема

Время работы $\operatorname{build}$ есть $\Theta(n)$.

Доказательство

Воспользуемся более точной оценкой времени работы $\operatorname{siftUp}$: пусть $\lfloor\log n\rfloor=k$, то есть $2^{k} \leqslant n < 2^{k+1}$. Высоту один имеет $n-2^{k}+1 \leqslant 2^{k}$ вершин. Высоту $1 < h \leqslant k+1$ имеет $2^{k+2-h}-2^{k+1-h}=2^{k+1-h}$ вершин. Тогда время работы $\operatorname{build}$ есть

$$ \begin{aligned} & O\left(\sum_{h=1}^{k+1} 2^{k+1-h} \cdot h\right)=O\left(n \cdot \sum_{h=1}^{k+1} \frac{h}{2^{h}}\right)=O\left(n \cdot \sum_{j=1}^{k+1} \sum_{h=j}^{k+1} \frac{1}{2^{h}}\right)= \\ & =O\left(n \cdot \sum_{j=1}^{k+1} \frac{1}{2^{j}} \cdot \frac{1}{1-\frac{1}{2}}\right)=O\left(n \cdot \frac{1}{1-\frac{1}{2}} \cdot \frac{1}{1-\frac{1}{2}}\right)=O(n) \end{aligned} $$

Heapsort

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

1
2
3
4


heapSort(a, n):
    build(a, n) # строим кучу, в корне которой хранится максимум
    for i = 0..(n - 1):
        extractMax()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


def heapSort(a, n):
    # Строим кучу, в корне которой хранится максимум
    build(a, n)
    
    for i in range(n - 1, 0, -1):
        # Обмениваем корень (максимум) с последним элементом
        a[0], a[i] = a[i], a[0]
        # Уменьшаем размер кучи и восстанавливаем свойство кучи
        siftDown(a, 0, i)

def build(a, n):
    # Начинаем с последнего родителя и идем к корню
    for i in range(n // 2 - 1, -1, -1):
        siftDown(a, i, n)

def siftDown(a, i, n):
    largest = i
    left = 2 * i + 1  # левый потомок (в 0-индексации)
    right = 2 * i + 2  # правый потомок
    
    # Если левый потомок больше корня
    if left < n and a[left] > a[largest]:
        largest = left
    
    # Если правый потомок больше, чем самый большой элемент на данный момент
    if right < n and a[right] > a[largest]:
        largest = right
    
    # Если самый большой элемент не корень
    if largest != i:
        a[i], a[largest] = a[largest], a[i]  # меняем местами
        # Рекурсивно просеиваем затронутую подкучу
        siftDown(a, largest, n)


# Пример использования
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    heapSort(arr, len(arr))
    print("Отсортированный массив:", arr)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


#include <iostream>
#include <vector>

void siftDown(std::vector<int>& a, int i, int n) {
    int largest = i;
    int left = 2 * i + 1;  // левый потомок (в 0-индексации)
    int right = 2 * i + 2; // правый потомок
    
    // Если левый потомок больше корня
    if (left < n && a[left] > a[largest]) {
        largest = left;
    }
    
    // Если правый потомок больше, чем самый большой элемент на данный момент
    if (right < n && a[right] > a[largest]) {
        largest = right;
    }
    
    // Если самый большой элемент не корень
    if (largest != i) {
        std::swap(a[i], a[largest]);  // меняем местами
        // Рекурсивно просеиваем затронутую подкучу
        siftDown(a, largest, n);
    }
}

void build(std::vector<int>& a, int n) {
    // Начинаем с последнего родителя и идем к корню
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(a, i, n);
    }
}

void heapSort(std::vector<int>& a, int n) {
    // Строим кучу, в корне которой хранится максимум
    build(a, n);
    
    for (int i = n - 1; i > 0; i--) {
        // Обмениваем корень (максимум) с последним элементом
        std::swap(a[0], a[i]);
        // Уменьшаем размер кучи и восстанавливаем свойство кучи
        siftDown(a, 0, i);
    }
}

// Пример использования
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();
    
    heapSort(arr, n);
    
    std::cout << "Отсортированный массив: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

✍️ Heapsort не является стабильной сортировкой.

Очередь с приоритетами

Очередь с приоритетами (priority queue) отличается от обычной очереди тем, что у каждого элемента есть приоритет, и извлекается не тот элемент, что был добавлен в очередь раньше всех, а элемент с максимальным приоритетом. Встроенная в C++ реализация очереди с приоритетами - std::priority_queue.

Потребность в использовании очереди с приоритетами возникает, например, при планировании задач в многозадачных операционных системах (процессы с большим приоритетом нужно выполнить раньше). Также очередь с приоритетами используется во многих алгоритмах, некоторые из которых нам ещё встретятся.

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

Удаление или изменение произвольного элемента

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

Если приоритет объекта не максимален, то сложно быстро понять, где именно в куче он находится. Поэтому когда возникает потребность в таких операциях, обычно для каждого объекта дополнительно поддерживается ссылка на его позицию в куче (обычно это просто номер этой позиции), а для каждой позиции в куче поддерживается ссылка на объект, который находится в этой позиции. Так, если объекты пронумерованы числами от $1$ до $n$, можно поддерживать массив pos, в $i$-й ячейке которого будет храниться позиция в куче элемента с номером $i$. При перестройке кучи этот массив несложно пересчитывать.

Итак, пусть мы хотим удалить объект из кучи $a$ размера $n$, при этом мы знаем, что сейчас он находится на позиции $i$. Поступим так же, как и при удалении максимума: поменяем $i$-й элемент местами с последним, и уменьшим размер кучи. После этого $a$ может перестать быть кучей, но $i$-й элемент можно либо увеличить, либо уменьшить так, что $a$ снова станет кучей (например, можно вернуть старое значение $i$-го элемента). Значит после вызова $\operatorname{siftUp(i)}$ или $\operatorname{siftDown(i)}$ $a$ снова станет кучей. Если мы вызовем обе операции, то одна из них “починит” кучу, а вторая ничего не сделает. Время работы $O(\log n)$.

1
2
3
4
5
6


delete(i):
    swap(a[i], a[sz])
    sz -= 1
    if i <= sz:
        siftUp(i)
        siftDown(i)

Точно так же можно менять значение приоритета у произвольного объекта. Пусть объект находится в куче в позиции $i$, тогда поменяем значение приоритета и снова запустим $\operatorname{siftUp(i)}$, $\operatorname{siftDown(i)}$. Это работает ровно по тем же причинам, что и в случае удаления. Время работы снова $O(\log n)$.

1
2
3
4


change(i, x):
    a[i] = x
    siftUp(i)
    siftDown(i)

✍️ Существуют и более сложные кучи, обладающие различными дополнительными полезными свойствами. Фибоначчиевы кучи (Fredman, Tarjan, 1987) известны тем, что позволяют в среднем за $O(1)$ не только находить минимум, но и добавлять новый элемент, а также уменьшать значение элемента. Удаление работает в среднем за $O(\log n)$. Использование фибоначчиевой кучи позволяет улучшить теоретическую оценку времени работы некоторых алгоритмов. Проблема в том, что из-за сложности реализации и большой константы в оценке времени работы на практике фибоначчиевы кучи, как правило, работают не быстрее обычных, поэтому практически не применяются и имеют скорее теоретическую ценность.