Продвинутый модуль: сливаемые и Фибоначчиевы кучи

Это продвинутый модуль после двоичной кучи. Для основного маршрута можно сразу перейти к динамическому программированию. Начнём с факультативного сценария: у команды A задачи с приоритетами [2,7,9], у B — [1,5]. После meld все пять задач находятся в одной очереди, ближайшая имеет приоритет 1. Вставлять их по одной не обязательно: объединённый массив обычных куч можно обработать heapify за O(n+m).

Теперь задача с id=17 стала срочной: её приоритет уменьшаем с 7 до 0 через decreaseKey(handle,0). Handle — сохранённая ссылка или устойчивый id именно этой задачи; одинаковые приоритеты не делают задачи одинаковыми. Приоритет меньше — задача раньше. Специализированный meld полезен, когда большие очереди приходится объединять многократно.

Для одного слияния heapify часто достаточно. Чтобы выбирать структуру для множества запросов, сначала построим несколько вариантов кучи и их инварианты, затем сравним оценки в конце. В разминке meld_values вы проверите сохранение содержимого, в профильной задаче — устройство самого meld.

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

При уменьшении ключа новое значение не превосходит прежнего, так что свойство min-кучи может нарушиться только по отношению к родителю.

Handle — ссылка или устойчивый идентификатор уже найденного узла. Если его нет, поиск элемента в куче может стоить O(n), и оценку decreaseKey нельзя считать полной ценой запроса. Meld обычно разрушает независимость исходных куч: после него владельцы и время жизни узлов должны быть определены. Для двоичной кучи два массива можно объединить и построить заново за O(n+m), а не обязательно за O(m log(n+m)).

import heapq

def updated_priorities(initial, updates):
    current = dict(enumerate(initial))
    heap = [(key, i) for i, key in current.items()]
    heapq.heapify(heap)
    for i, key in updates:
        if key < current[i]:
            current[i] = key
            heapq.heappush(heap, (key, i))
    result = []
    while heap:
        key, i = heapq.heappop(heap)
        if current.get(i) == key:
            result.append(key)
            del current[i]
    return result

print(*updated_priorities([9, 5], [(0, 2)]))

use std::cmp::Reverse;
use std::collections::{BinaryHeap,HashMap};
fn updated_priorities(initial:&[i64],updates:&[(usize,i64)])->Vec<i64>{
    let mut current:HashMap<usize,i64>=initial.iter().copied().enumerate().collect();
    let mut heap:BinaryHeap<Reverse<(i64,usize)>>=current.iter().map(|(&i,&key)|Reverse((key,i))).collect();
    for &(i,key)in updates{if key<current[&i]{current.insert(i,key);heap.push(Reverse((key,i)));}}
    let mut result=Vec::new();while let Some(Reverse((key,i)))=heap.pop(){if current.get(&i)==Some(&key){result.push(key);current.remove(&i);}}
    result
}
fn main(){println!("{}",updated_priorities(&[9,5],&[(0,2)]).iter().map(|x|x.to_string()).collect::<Vec<_>>().join(" "));}

2 5

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

Построим форму по шагам. B₀ — один узел. Два одноузловых дерева соединяем под меньшим корнем: B₁ содержит 2 узла. Два B₁ дают B₂ с 4 узлами; два B₂ — B₃ с 8. Ранг k просто называет этот шаг построения. Только после этих четырёх картинок обобщим правило до 2ᵏ узлов.

Биномиальное дерево Bₖ (Binomial tree) — Дерево, построенное связыванием двух деревьев Bₖ₋₁, одно становится ребёнком другого.

В дереве Bₖ содержится 2ᵏ узлов; у корня k детей, являющихся корнями B₀, B₁, …, Bₖ₋₁. Для min-кучи каждый родитель не превосходит своих детей.

Дерево B₀ состоит из одной вершины. Связав два B₂ под меньшим корнем, получим B₃ с восемью вершинами и тремя детьми у корня. Операция link сохраняет порядок min-кучи и занимает O(1), если список детей позволяет добавить ссылку без копирования.

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

У 13 элементов естественное разложение 13=8+4+1: берём B₃, B₂ и B₀. В двоичной записи 13=1101₂ единицы стоят ровно в разрядах 3, 2, 0. Биномиальная куча хранит не больше одного дерева каждого ранга. Слияние — сложение таких записей с переносами.

Биномиальная куча (Binomial heap) — Лес min-деревьев разных рангов: на каждый ранг допускается не более одного дерева.

Для n элементов набор рангов определяется единичными разрядами двоичной записи n. Поэтому деревьев не более O(log n).

Операция meld действует как сложение двоичных чисел: два дерева одинакового ранга связывают в одно дерево следующего ранга. Минимум находится среди корней.

link(a, b):
    assert a.rank == b.rank
    if a.key > b.key: swap(a,b)
    make b a child of a
    a.rank += 1
    return a

Например, 13 = 8 + 4 + 1: куча содержит ранги 3, 2 и 0. При добавлении одного узла ранг 0 переносится в 1; если он занят, перенос идёт дальше. Без отдельного указателя минимум ищется среди O(log n) корней. Отдельный указатель ускоряет чтение минимума, но его нужно обновлять после изменений.

def binomial_ranks(n):
    ranks = []
    rank = 0
    while n:
        if n & 1:
            ranks.append(rank)
        n >>= 1
        rank += 1
    return ranks

print(*binomial_ranks(13))

fn binomial_ranks(mut n:u64)->Vec<u32>{let mut result=Vec::new();let mut rank=0;while n>0{if n&1==1{result.push(rank);}n>>=1;rank+=1;}result}
fn main(){println!("{}",binomial_ranks(13).iter().map(|x|x.to_string()).collect::<Vec<_>>().join(" "));}

0 2 3

Немедленные переносы дают логарифмическое слияние. Посмотрим, что можно отложить до удаления минимума.

def binomial_ranks(n):
	# Напишите решение
	pass

Если часто объединять большие очереди и уменьшать приоритеты уже известных задач, немедленные переносы биномиальной кучи повторяют работу. Фибоначчиева куча откладывает её: добавление и слияние увеличивают число корней, но не требуют немедленной консолидации. Это улучшает теоретический бюджет некоторых последовательностей операций; указатели, память и константы не обещают практического выигрыша на каждом входе.

Фибоначчиева куча (Fibonacci heap) — Лес деревьев min-кучи с ленивым объединением и амортизированными гарантиями для ключевых операций.

Фибоначчиева куча ослабляет жёсткую форму биномиальных деревьев. При insert новый элемент можно просто сделать отдельным корнем; при meld соединить корневые списки.

Указатель на минимальный корень позволяет отвечать getMin за O(1). Дорогую нормализацию рангов откладывают до extractMin.

Нужны циклические двусвязные списки корней и детей, parent, степень и отметка у узла, а также указатель min. Операции insert и meld требуют O(1) реальных переназначений; одинаковые степени корней до консолидации разрешены. Корни не помечаем, а структура каждого дерева сохраняет порядок min-кучи.

Дешёвое добавление накапливает корни. Разберём операцию, которая приводит их к управляемому виду.

Отложенная работа всё же должна когда-то выполняться. Извлечение минимума удаляет корень, выводит его детей в корневой список и объединяет деревья одинаковой степени.

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

После консолидации заново выбирается минимальный корень. Чтобы время было логарифмическим, надо доказать, что ранг узла ограничен O(log n), несмотря на возможные удаления детей.

После n последовательных вставок корней может быть n, поэтому одно extractMin действительно может стоить Θ(n). Логарифмической является амортизированная цена, а не худший случай этого вызова. Ограничение степени получают из того, что некорневой узел может потерять не более одного ребёнка, оставаясь на месте: минимальное число потомков растёт как числа Фибоначчи.

Для логарифмической степени нужен контроль потерь детей. Он определит правила уменьшения ключа.

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

Если после decreaseKey ключ узла стал меньше родительского, узел отрезают от родителя и переводят в корневой список. Чтобы дерево не слишком сильно деградировало, вводят пометки потерь ребёнка.

Первая потеря ребёнка у некорневого узла помечает его; повторная запускает разрезание самого этого узла и может продолжиться вверх — это каскадное разрезание.

При первой потере ребёнка некорневой узел помечается. При второй он сам становится корнем, пометка снимается, и проверка продолжается у его родителя. Если уменьшенный ключ всё ещё не меньше родительского, разрезание не нужно. При переносе ребёнка в корни у него сбрасываются parent и mark.

Правила пометок заданы. Осталось объяснить, кто оплачивает длинное каскадное разрезание.

Фибоначчиева куча даёт сильные теоретические оценки, но её реализация сложна. Для многих контестных задач со слиянием подходит более простой вариант — левосторонняя куча с коротким правым путём.

Левосторонняя куча (Leftist heap) — Двоичная min-куча с ограничением на длины кратчайших путей к пустым детям: npl(left) ≥ npl(right).

Корень min-кучи содержит минимум. Операция meld сравнивает корни, сохраняет меньший, рекурсивно сливает правое поддерево с другой кучей и при необходимости меняет детей местами.

meld(a,b):
    if a == null: return b
    if b == null: return a
    if a.key > b.key: swap(a,b)
    a.right = meld(a.right,b)
    if npl(a.left) < npl(a.right): swap(a.left,a.right)
    update_npl(a)
    return a

Примем npl(null) = −1, npl(листа) = 0 и npl(v) = 1 + min(npl(left), npl(right)). Инвариант npl(left) ≥ npl(right) делает кратчайший путь к пустому ребёнку правым. При слиянии рекурсивно обрабатываются только правые пути; затем дети при необходимости меняются местами. Высота всего дерева может быть линейной, а правый путь остаётся O(log n). Для insert сливаем с одноузловой кучей, для extractMin — двух детей корня.

В сравнении n и m — размеры двух сливаемых куч. Для динамического массива рост ёмкости учитывается амортизированно и отмечен звёздочкой. Meld потребляет две независимые кучи. Поиск произвольного значения и чтение максимума в min-куче обычно стоят O(n); вставка в заданную позицию не предусмотрена. Для биномиальной кучи отдельный обновляемый указатель min даёт O(1) чтение минимума.

class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.rank = key, None, None, 0

def rank(node):
    return node.rank if node is not None else -1

def meld(a, b):
    if a is None: return b
    if b is None: return a
    if a.key > b.key: a, b = b, a
    a.right = meld(a.right, b)
    if rank(a.left) < rank(a.right): a.left, a.right = a.right, a.left
    a.rank = rank(a.right) + 1
    return a

def make_heap(values):
    root = None
    for x in values: root = meld(root, Node(x))
    return root

def drain(root):
    result = []
    while root is not None:
        result.append(root.key)
        root = meld(root.left, root.right)
    return result

print(*drain(meld(make_heap([3, 8, 7]), make_heap([1, 9, 4]))))

type Link=Option<Box<Node>>;
struct Node{key:i64,left:Link,right:Link,rank:i32}
fn rank(node:&Link)->i32{node.as_ref().map_or(-1,|x|x.rank)}
fn meld(a:Link,b:Link)->Link{
    let(mut a,b)=match(a,b){(None,b)=>return b,(a,None)=>return a,(Some(a),Some(b))=>(a,b)};
    if a.key>b.key{return meld(Some(b),Some(a));}
    a.right=meld(a.right.take(),Some(b));
    if rank(&a.left)<rank(&a.right){std::mem::swap(&mut a.left,&mut a.right);}
    a.rank=rank(&a.right)+1;Some(a)
}
fn make_heap(values:&[i64])->Link{let mut root=None;for &key in values{root=meld(root,Some(Box::new(Node{key,left:None,right:None,rank:0})));}root}
fn drain(mut root:Link)->Vec<i64>{let mut result=Vec::new();while let Some(mut node)=root{result.push(node.key);root=meld(node.left.take(),node.right.take());}result}
fn main(){let result=drain(meld(make_heap(&[3,8,7]),make_heap(&[1,9,4])));println!("{}",result.iter().map(|x|x.to_string()).collect::<Vec<_>>().join(" "));}

1 3 4 7 8 9

Выбор кучи зависит от набора запросов и констант реализации. Закрепим оценки по ограничениям; в следующей лекции будем ускорять не хранение, а повторные вычисления.

def meld_values(a, b):
	# Напишите решение
	pass

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

Общий справочник всех лекций ↗

Найдено: 13 из 13

Сначала подставьте максимальные размеры из условия в оценку времени и памяти. Оценка числа действий — ориентир: константы, язык и ввод проверяются отдельно.

Сначала посчитайте типы операций

Пусть I вставок, M слияний, D уменьшений и E извлечений. Сравнивайте сумму цен, а не одну строку таблицы. У Фибоначчиевой кучи I+M+D оплачиваются амортизированно за O(I+M+D), а извлечения добавляют O(E log n). Нужны уже известные handle.

Ленивая двоичная куча — другой бюджет

При 200 000 обновлений расстояний можно хранить до O(q) записей, включая устаревшие. Время зависит от log q, память — от числа обновлений. Сравните это с лимитом, прежде чем писать сложную указательную кучу.

Две двоичные кучи можно объединить линейным heapify объединённого массива. Это полезно для одного крупного слияния; много повторных слияний больших контейнеров могут сделать суммарную линейную по размеру работу квадратичной.

Ранги, правый путь и память

У левосторонней кучи O(log n) относится к правому пути, а не к высоте всего дерева. Не используйте обычный рекурсивный обход всего дерева, считая его глубину логарифмической. Для освобождения или проверки глубокой структуры может понадобиться явный стек.

При n,m ≤ 100 000 в P3377 нельзя каждый раз копировать все значения объединяемых куч. Храните узлы и ссылки, проверяйте удалённые id, повторы значений и попытку слить кучу саму с собой. При равных ключах условие может требовать сравнения пары (ключ, исходный id).

Разминка: содержимое слияния

Сначала решите meld_values: это упражнение на сохранение всех значений и повторов. Оно не проверяет дерево. Основной результат модуля — следующий meld, в котором тесты проверяют min-порядок и npl после каждой операции.

def meld_values(a, b):
	# Напишите решение
	pass

Основное применение: настоящее левостороннее дерево

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right
        self.npl = 1 + (right.npl if right else -1)

def meld(a, b):
    # Допишите только эту функцию. npl(None) = -1.
    pass

# Готовый адаптер: вход — [key, left, right], пустое дерево — None.
def _decode(tree):
    return None if tree is None else Node(tree[0], _decode(tree[1]), _decode(tree[2]))

def _valid(root):
    stack, seen = [root], set()
    while stack:
        node = stack.pop()
        if node is None: continue
        if id(node) in seen: return False
        seen.add(id(node))
        l = node.left.npl if node.left else -1
        r = node.right.npl if node.right else -1
        if l < r or node.npl != 1 + r: return False
        for child in (node.left, node.right):
            if child and child.key < node.key: return False
            stack.append(child)
    return True

def leftist_probe(a, b):
    root = meld(_decode(a), _decode(b))
    values, valid = [], True
    for _ in range(256):
        valid = valid and _valid(root)
        if not valid or root is None: break
        values.append(root.key)
        root = meld(root.left, root.right)
    return {"valid": valid and root is None, "values": values}

Профильное испытание

P3377 добавляет доступ по исходным id и удаление. Перед ней проверьте свою реализацию на пустой куче, равных ключах и чередовании meld/extractMin.

Примените разобранные приёмы самостоятельно. Для каждой задачи сначала сформулируйте требования к ответу и предложите простое решение. Затем подставьте максимальные ограничения, оцените время и память и решите, какое улучшение требуется. Подсказки с идеей и оценкой раскрываются отдельно.

Уровни задают порядок практики в курсе, а не единую шкалу платформ. Если уровень отличается от отметки LeetCode, это указано в карточке. Для Codeforces используется оценка курса.

Графы с частым уменьшением расстояний используют decreaseKey; сравнение с ленивой двоичной кучей теперь можно проводить по конкретному бюджету операций.