Рандомізована купа

Рандомізована купа — це купа, яка завдяки використанню рандомізації дозволяє виконувати всі операції за очікуваний логарифмічний час.

Мінімальна купа — це бінарне дерево, у якому значення кожної вершини менше або дорівнює значенням її дітей. Таким чином, мінімум дерева завжди міститься в кореневій вершині.

Максимальну купу можна означити аналогічно: замінивши «менше» на «більше».

Стандартні операції купи такі:

• Додавання значення
• Витягування мінімуму
• Видалення мінімуму
• Злиття двох куп (без видалення дублікатів)
• Видалення довільного елемента (якщо відома його позиція в дереві)

Рандомізована купа може виконувати всі ці операції за очікуваний час $O(\log n)$ з дуже простою реалізацією.

Коли підходить цей алгоритм?

• Чи потрібна вам операція злиття двох куп (mergeable heap), якої немає у звичайній бінарній купі?
• Чи влаштовує очікувана (а не гарантована) складність $O(\log n)$ заради дуже простої реалізації?
• Якщо злиття не потрібне, а потрібні лише вставка/витягування мінімуму, чи не простіше взяти стандартну бінарну купу (priority_queue)?

Структура даних

Ми можемо одразу описати структуру бінарної купи:

C++

struct Tree {
    int value;
    Tree * l = nullptr;
    Tree * r = nullptr;
};

Python

class Tree:
    def __init__(self, value: int):
        # У вершині зберігаємо значення та вказівники на нащадків
        self.value = value
        self.l: "Tree | None" = None  # лівий нащадок (None, якщо відсутній)
        self.r: "Tree | None" = None  # правий нащадок (None, якщо відсутній)

TypeScript

class Tree {
  value: number;
  l: Tree | null = null; // лівий нащадок (null, якщо відсутній)
  r: Tree | null = null; // правий нащадок (null, якщо відсутній)

  constructor(value: number) {
    this.value = value;
  }
}

Go

type Tree struct {
    value int
    l     *Tree // лівий нащадок (nil, якщо відсутній)
    r     *Tree // правий нащадок (nil, якщо відсутній)
}

У вершині ми зберігаємо значення. Крім того, у нас є вказівники на лівого та правого нащадка, які вказують на null, якщо відповідного нащадка не існує.

Операції

Неважко бачити, що всі операції можна звести до однієї: злиття двох куп в одну. Дійсно, додавання нового значення до купи рівносильне злиттю купи з купою, що складається з єдиної вершини з цим значенням. Пошук мінімуму взагалі не потребує жодної операції — мінімум це просто значення в корені. Видалення мінімуму рівносильне результату злиття лівого та правого нащадків кореневої вершини. А видалення довільного елемента відбувається аналогічно. Ми зливаємо нащадків вершини й замінюємо вершину результатом злиття.

Отже, насправді нам потрібно реалізувати лише операцію злиття двох куп. Усі інші операції тривіально зводяться до цієї операції.

Нехай задано дві купи $T_1$ та $T_2$. Зрозуміло, що корінь кожної з цих куп містить її мінімум. Тому коренем результуючої купи буде мінімум із цих двох значень. Отже, ми порівнюємо обидва значення й використовуємо менше з них як новий корінь. Тепер нам потрібно об'єднати нащадків обраної вершини з рештою купи. Для цього ми обираємо одного з нащадків і зливаємо його з рештою купи. Таким чином, ми знову маємо операцію злиття двох куп. Рано чи пізно цей процес завершиться (кількість таких кроків обмежена сумою висот двох куп).

Щоб досягти логарифмічної складності в середньому, нам потрібно задати спосіб вибору одного з двох нащадків так, щоб середня довжина шляху була логарифмічною. Неважко здогадатися, що ми будемо приймати це рішення випадково. Таким чином, реалізація операції злиття виглядає так:

C++

Tree* merge(Tree* t1, Tree* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t2->value < t1->value)
        swap(t1, t2);
    if (rand() & 1)
        swap(t1->l, t1->r);
    t1->l = merge(t1->l, t2);
    return t1;
}

Python

import random


def merge(t1: "Tree | None", t2: "Tree | None") -> "Tree | None":
    # Якщо одна з куп порожня — повертаємо іншу
    if t1 is None or t2 is None:
        return t1 if t1 is not None else t2
    # Робимо t1 тією купою, що має менше значення в корені
    if t2.value < t1.value:
        t1, t2 = t2, t1
    # Випадково обмінюємо нащадків t1
    if random.random() < 0.5:
        t1.l, t1.r = t1.r, t1.l
    # Зливаємо лівого нащадка t1 з рештою купи
    t1.l = merge(t1.l, t2)
    return t1

TypeScript

function merge(t1: Tree | null, t2: Tree | null): Tree | null {
  // Якщо одна з куп порожня — повертаємо іншу
  if (t1 === null || t2 === null) {
    return t1 !== null ? t1 : t2;
  }
  // Робимо t1 тією купою, що має менше значення в корені
  if (t2.value < t1.value) {
    [t1, t2] = [t2, t1];
  }
  // Випадково обмінюємо нащадків t1
  if (Math.random() < 0.5) {
    [t1.l, t1.r] = [t1.r, t1.l];
  }
  // Зливаємо лівого нащадка t1 з рештою купи
  t1.l = merge(t1.l, t2);
  return t1;
}

Go

import "math/rand"

func merge(t1, t2 *Tree) *Tree {
    // Якщо одна з куп порожня — повертаємо іншу
    if t1 == nil || t2 == nil {
        if t1 != nil {
            return t1
        }
        return t2
    }
    // Робимо t1 тією купою, що має менше значення в корені
    if t2.value < t1.value {
        t1, t2 = t2, t1
    }
    // Випадково обмінюємо нащадків t1
    if rand.Intn(2) == 1 {
        t1.l, t1.r = t1.r, t1.l
    }
    // Зливаємо лівого нащадка t1 з рештою купи
    t1.l = merge(t1.l, t2)
    return t1
}

Спочатку ми перевіряємо, чи одна з куп порожня, — тоді нам взагалі не потрібно виконувати жодної дії злиття. Інакше ми робимо купою t1 ту, що має менше значення (обмінюючи t1 та t2, якщо це потрібно). Ми хочемо злити лівого нащадка t1 з t2, тому ми випадково обмінюємо нащадків t1, а потім виконуємо злиття.

Складність

Введемо випадкову величину $h(T)$, яка позначатиме довжину випадкового шляху від кореня до листа (довжину в кількості ребер). Зрозуміло, що алгоритм merge виконує $O(h(T_1) + h(T_2))$ кроків. Тому, щоб зрозуміти складність операцій, ми маємо дослідити випадкову величину $h(T)$.

Математичне сподівання

Ми припускаємо, що сподівання $h(T)$ можна оцінити зверху логарифмом кількості вершин у купі:

$$\mathbf{E} h(T) \le \log(n+1)$$

Це легко довести за індукцією. Нехай $L$ та $R$ — ліве та праве піддерева кореня $T$, а $n_L$ та $n_R$ — кількість вершин у них ($n = n_L + n_R + 1$).

Нижче наведено крок індукції:

$$\begin{align} \mathbf{E} h(T) &= 1 + \frac{\mathbf{E} h(L) + \mathbf{E} h(R)}{2} \le 1 + \frac{\log(n_L + 1) + \log(n_R + 1)}{2} \\\\ &= 1 + \log\sqrt{(n_L + 1)(n_R + 1)} = \log 2\sqrt{(n_L + 1)(n_R + 1)} \\\\ &\le \log \frac{2\left((n_L + 1) + (n_R + 1)\right)}{2} = \log(n_L + n_R + 2) = \log(n+1) \end{align}$$

Перевищення математичного сподівання

Звичайно, ми ще не задоволені. Математичне сподівання $h(T)$ нічого не говорить про найгірший випадок. Усе ще можливо, що для конкретного дерева шляхи від кореня до вершин у середньому значно більші за $\log(n + 1)$.

Доведемо, що ймовірність перевищення математичного сподівання справді дуже мала:

$${\cal P}(h(T) > (c+1) \log n) < \frac{1}{n^c}$$

для будь-якої додатної сталої $c$.

Тут ми позначаємо через $P$ множину шляхів від кореня купи до листків, довжина яких перевищує $(c+1) \log n$. Зауважимо, що для будь-якого шляху $p$ довжини $|p|$ ймовірність того, що він буде обраний як випадковий шлях, дорівнює $2^{-|p|}$. Тому ми отримуємо:

$${\cal P}(h(T) > (c+1) \log n) = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$$

Складність алгоритму

Таким чином, алгоритм merge, а отже й усі інші операції, виражені через нього, можуть бути виконані за $O(\log n)$ у середньому.

Більше того, для будь-якої додатної сталої $\epsilon$ існує така додатна стала $c$, що ймовірність того, що операція потребуватиме більше ніж $c \log n$ кроків, менша за $n^{-\epsilon}$ (у певному сенсі це описує поведінку алгоритму в найгіршому випадку).