Двойная куча

Две кучи («двойная куча») — что это и зачем она нужна

Определение

Двойная куча — это пара приоритетных очередей:

Левая часть	Правая часть
max-heap → хранит меньшие элементы	min-heap → хранит большие элементы

Между ними проходит «граница» набора данных; корни куч «касаются» середины.

Инварианты, которые нужно поддерживать

1. Размеры отличаются ≤ 1

   |maxHeap| ≈ |minHeap|

2. Каждый элемент max-heap ≤ каждый элемент min-heap

   maxHeap.top() ≤ minHeap.top()

При нечётном количестве элементов «лишний» кладут в max-heap (договорились так ради удобства; можно и наоборот).

Зачем это нужно

Такая связка решает задачи, где нужно быстро узнавать медиану или вообще динамический «центр» массива, пока данные постоянно добавляются или удаляются.

• Примеры:

  • 295. Find Median from Data Stream — медиана растущего потока.
  • 480. Sliding Window Median — медиана «бегущего» окна фиксированного размера.

С одной кучей можно мгновенно брать минимум/максимум; с двумя — ещё и середину.

Базовый шаблон операций

addNum(x):
    push x → maxHeap
    push pop(maxHeap) → minHeap        // перенос «лишнего большого» вправо
    if |minHeap| > |maxHeap|:          // выравниваем размеры
        push pop(minHeap) → maxHeap

findMedian():
    если |maxHeap| > |minHeap|:
        return maxHeap.top()
    иначе:
        return (maxHeap.top() + minHeap.top()) / 2

• addNum — O(log n) (два-три обращения к кучам).
• findMedian — O(1).

Когда брать двойную кучу вместо других структур

Сценарий	Две кучи	Альтернатива
нужен только быстрый add + median	✅	—
нужны удаление произвольного элемента	△ — возможно, но сложнее (нужно ленивое удаление)	сбалансированное BST / multiset
строгие ограничения на память	✅ — хранит ровно все элементы	—

Преимущества

• Константная выдача медианы.
• Простая реализация на любой платформе, где куча уже есть.
• Расширяется на задачи с «большей» и «меньшей» половиной (k-я статистика, разделение по порогу и т. д.).

Find Median from Data Stream

Условие задачи

Нужно реализовать класс MedianFinder, который поддерживает две операции:

Метод	Описание
addNum(num)	добавляет число num во внутреннюю структуру данных
findMedian()	возвращает медиану всех добавленных чисел

Медиана — это середина отсортированного списка. Если элементов чётное количество, берётся среднее двух серединных значений.

---

Ключевая идея

Поддерживаем две кучи:

• max-heap хранит меньшую половину элементов. Корень = самое большое число из этой половины.
• min-heap хранит большую половину элементов. Корень = самое маленькое число из этой половины.

Состояние кучи после каждой вставки:

max-heap (левая часть)          min-heap (правая часть)

        13                                  36
      /    \                              /     \
     7      3                           50       100
    /                                 /
   1                                 42

Правила поддержания инвариантов:

1. Размеры куч отличаются не более чем на 1 элемент.
2. Все элементы max-heap ≤ все элементы min-heap.

Если общее число элементов нечётное, «лишний» элемент держим в max-heap. Медиана тогда:

• при нечётном количестве — root(max-heap)
• при чётном — среднее значений root(max-heap) и root(min-heap)

---

Алгоритм вставки числа

1. push в max-heap.
2. pop из max-heap, push результат в min-heap — перенос «слишком большого» элемента вправо.
3. Если min-heap.size() > max-heap.size(), pop из min-heap, push результат в max-heap — выравниваем размеры.

Эти шаги одновременно обеспечивают оба инварианта.

---

Реализация на JavaScript

В JS нет встроенной приоритетной очереди, поэтому используем пакет @datastructures-js/priority-queue, где уже есть MaxPriorityQueue и MinPriorityQueue.

import {
  MaxPriorityQueue,
  MinPriorityQueue,
} from "@datastructures-js/priority-queue";

class MedianFinder {
  constructor() {
    this.minQueue = new MinPriorityQueue({ priority: (v) => v });
    this.maxQueue = new MaxPriorityQueue({ priority: (v) => v });
  }

  addNum(num) {
    this.maxQueue.enqueue(num);
    this.minQueue.enqueue(this.maxQueue.dequeue().element);
    if (this.minQueue.size() > this.maxQueue.size()) {
      this.maxQueue.enqueue(this.minQueue.dequeue().element);
    }
  }

  findMedian() {
    if (this.maxQueue.size() > this.minQueue.size()) {
      return this.maxQueue.front().element;
    }
    return (this.maxQueue.front().element + this.minQueue.front().element) / 2;
  }
}

---

Анализ сложности

Операция	Время	Память
addNum	O(log n)	O(n)
findMedian	O(1)	O(n)

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

---

Визуальная иллюстрация баланса куч

После вставок: 1, 3, 7, 13, 36, 100
┌───────────────┬───────────────┐
│   max-heap    │   min-heap    │
├─────┬─────┬───┼─────┬─────┬───┤
│  7  │  3  │ 1 │  36 │ 100 │   │
└─────┴─────┴───┴─────┴─────┴───┘
median = (7 + 36) / 2 = 21.5

Добавляем 50
┌───────────────┬───────────────┐
│   max-heap    │   min-heap    │
├─────┬─────┬───┼─────┬─────┬───┤
│ 13  │  7  │ 3 │ 36  │ 50  │100│
└─────┴─────┴───┴─────┴─────┴───┘
median = 13

Такая организация позволяет мгновенно брать медиану и поддерживать баланс с логарифмическими затратами на добавление.