Пирамиды (кучи)

живой пример

import java.util.Arrays;

public class HeapInsert {
    public static void main(String[] args) {
        int[] heap = new int[8];
        int size = 0;
        for (int value : new int[]{30, 90, 70, 50}) {
            int i = size++;
            heap[i] = value;
            while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
                int parent = (i - 1) / 2;
                int tmp = heap[i];
                heap[i] = heap[parent];
                heap[parent] = tmp;
                i = parent;
            }
            System.out.println(value + " → " + Arrays.toString(Arrays.copyOf(heap, size)));
        }
    }
}

живой пример

package main

import "fmt"

func main() {
	heap := make([]int, 8)
	size := 0
	for _, value := range []int{30, 90, 70, 50} {
		i := size
		size++
		heap[i] = value
		for i > 0 && heap[(i-1)/2] < heap[i] {
			parent := (i - 1) / 2
			heap[i], heap[parent] = heap[parent], heap[i]
			i = parent
		}
		fmt.Println(value, "→", heap[:size])
	}
}

живой пример

const heap = [];
for (const value of [30, 90, 70, 50]) {
  let i = heap.push(value) - 1;
  while (i > 0 && heap[Math.floor((i - 1) / 2)] < heap[i]) {
    const parent = Math.floor((i - 1) / 2);
    [heap[i], heap[parent]] = [heap[parent], heap[i]];
    i = parent;
  }
  console.log(`${value} → [${heap.join(", ")}]`);
}

живой пример

heap: list[int] = []
for value in (30, 90, 70, 50):
    heap.append(value)
    i = len(heap) - 1
    while i > 0 and heap[(i - 1) // 2] < heap[i]:
        parent = (i - 1) // 2
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent
    print(value, "→", heap)

живой пример

import java.util.Arrays;

public class HeapPoll {
    static int[] heap = {90, 50, 70, 30, 40, 60};
    static int size = heap.length;

    static int poll() {
        int top = heap[0];
        heap[0] = heap[--size];
        int i = 0;
        while (2 * i + 1 < size) {
            int child = 2 * i + 1;
            if (child + 1 < size && heap[child + 1] > heap[child]) child++;
            if (heap[i] >= heap[child]) break;
            int tmp = heap[i]; heap[i] = heap[child]; heap[child] = tmp;
            i = child;
        }
        return top;
    }

    public static void main(String[] args) {
        System.out.println("забрали " + poll() + " → " + Arrays.toString(Arrays.copyOf(heap, size)));
        System.out.println("забрали " + poll() + " → " + Arrays.toString(Arrays.copyOf(heap, size)));
    }
}

живой пример

package main

import "fmt"

var heap = []int{90, 50, 70, 30, 40, 60}

func poll() int {
	top := heap[0]
	last := len(heap) - 1
	heap[0] = heap[last]
	heap = heap[:last]
	i := 0
	for 2*i+1 < len(heap) {
		child := 2*i + 1
		if child+1 < len(heap) && heap[child+1] > heap[child] {
			child++
		}
		if heap[i] >= heap[child] {
			break
		}
		heap[i], heap[child] = heap[child], heap[i]
		i = child
	}
	return top
}

func main() {
	fmt.Println("забрали", poll(), "→", heap)
	fmt.Println("забрали", poll(), "→", heap)
}

живой пример

const heap = [90, 50, 70, 30, 40, 60];

function poll() {
  const top = heap[0];
  heap[0] = heap.pop();
  let i = 0;
  while (2 * i + 1 < heap.length) {
    let child = 2 * i + 1;
    if (child + 1 < heap.length && heap[child + 1] > heap[child]) child++;
    if (heap[i] >= heap[child]) break;
    [heap[i], heap[child]] = [heap[child], heap[i]];
    i = child;
  }
  return top;
}

console.log(`забрали ${poll()} → [${heap.join(", ")}]`);
console.log(`забрали ${poll()} → [${heap.join(", ")}]`);

живой пример

heap = [90, 50, 70, 30, 40, 60]


def poll() -> int:
    top = heap[0]
    heap[0] = heap.pop()
    i = 0
    while 2 * i + 1 < len(heap):
        child = 2 * i + 1
        if child + 1 < len(heap) and heap[child + 1] > heap[child]:
            child += 1
        if heap[i] >= heap[child]:
            break
        heap[i], heap[child] = heap[child], heap[i]
        i = child
    return top


print("забрали", poll(), "→", heap)
print("забрали", poll(), "→", heap)

живой пример

import java.util.PriorityQueue;

public class TopK {
    public static void main(String[] args) {
        int[] views = {120, 7, 3400, 55, 980, 42, 1500, 61, 2200, 15};
        int k = 3;
        PriorityQueue<Integer> best = new PriorityQueue<>();
        for (int v : views) {
            if (best.size() < k) best.offer(v);
            else if (v > best.peek()) {
                best.poll();
                best.offer(v);
            }
        }
        System.out.println("топ-" + k + ": " + best + ", худший из лучших на вершине: " + best.peek());
    }
}

живой пример

package main

import (
	"container/heap"
	"fmt"
)

type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func main() {
	views := []int{120, 7, 3400, 55, 980, 42, 1500, 61, 2200, 15}
	k := 3
	best := &minHeap{}
	for _, v := range views {
		if best.Len() < k {
			heap.Push(best, v)
		} else if v > (*best)[0] {
			heap.Pop(best)
			heap.Push(best, v)
		}
	}
	fmt.Printf("топ-%d: %v, худший из лучших на вершине: %d\n", k, *best, (*best)[0])
}

живой пример

class MinHeap {
  a = [];
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(v) {
    const a = this.a;
    let i = a.push(v) - 1;
    while (i > 0 && a[(i - 1) >> 1] > a[i]) {
      const p = (i - 1) >> 1;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (2 * i + 1 < a.length) {
        let c = 2 * i + 1;
        if (c + 1 < a.length && a[c + 1] < a[c]) c++;
        if (a[i] <= a[c]) break;
        [a[i], a[c]] = [a[c], a[i]];
        i = c;
      }
    }
    return top;
  }
}

const views = [120, 7, 3400, 55, 980, 42, 1500, 61, 2200, 15];
const k = 3;
const best = new MinHeap();
for (const v of views) {
  if (best.size < k) best.push(v);
  else if (v > best.peek()) {
    best.pop();
    best.push(v);
  }
}
console.log(`топ-${k}: [${best.a.join(", ")}], худший из лучших на вершине: ${best.peek()}`);

живой пример

import heapq

views = [120, 7, 3400, 55, 980, 42, 1500, 61, 2200, 15]
k = 3
best: list[int] = []
for v in views:
    if len(best) < k:
        heapq.heappush(best, v)
    elif v > best[0]:
        heapq.heapreplace(best, v)
print(f"топ-{k}: {best}, худший из лучших на вершине: {best[0]}")
print("то же одной строкой:", heapq.nlargest(k, views))

Кучу почти никогда не пишут руками, но её устройство знать приходится: у готового класса есть поведение, которое удивляет всех, кто не знает, что внутри.

Эталонная реализация — PriorityQueue: ровно та двоичная куча, что описана выше, вплоть до формул по индексу и обоих обменов. Разница с нашим примером одна — по умолчанию куча минимальная: наверху оказывается наименьший элемент по естественному порядку. Нужен максимум — передают компаратор в конструктор.

Сложность предсказуемая: offer (вставка) и poll (выемка вершины) — O(log n), потому что элемент проходит путь от листа до корня или обратно; peek (посмотреть вершину, не забирая) — O(1), это просто нулевая ячейка массива. Место очередь берёт с запасом и расширяет сама: маленький массив удваивается, большой растёт примерно в полтора раза.

Две операции стоят дорого: contains и remove(Object) — O(n). Куча не знает, где лежит конкретное значение, — ей приходится просматривать весь массив. Нужно часто удалять произвольный элемент — чистая куча не подходит.

Нет у PriorityQueue и операции «изменить приоритет элемента, который уже внутри»: поменять поле у объекта в куче нельзя, куча об этом не узнает и сломает порядок, а remove с последующим offer стоит O(n) из-за поиска. Это главная грабля Дейкстры, и как её обходят, дописывая новый элемент вместо правки старого, разбирает статья про взвешенные графы.

Главная же грабля вот какая: обход PriorityQueue не отсортирован. Ни цикл for, ни toString, ни stream не выдают элементы по возрастанию — они идут в том порядке, в каком лежат в массиве, где действует лишь слабая упорядоченность. Гарантирован только один элемент — тот, что на вершине. Порядок появляется при выемке: элементы выходят через poll уже строго по возрастанию.

живой пример

import java.util.List;
import java.util.PriorityQueue;

public class QueueOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(List.of(5, 1, 9, 3));
        System.out.println(queue);        // [1, 3, 9, 5] — не отсортировано
        System.out.println(queue.peek()); // 1 — а вот это гарантия
        System.out.println(queue.poll() + ", " + queue.poll()); // 1, 3 — по возрастанию
    }
}

Кстати о конструкторе из примера: готовую коллекцию PriorityQueue не перекладывает по одному элементу, а превращает в кучу целиком — та самая O(N) вместо O(N·log N).

Ещё две мелочи: null в очередь класть нельзя, и PriorityQueue не потокобезопасна — для нескольких потоков берут PriorityBlockingQueue.

Кучу почти никогда не пишут руками, но её устройство знать приходится: у готового пакета есть поведение, которое удивляет всех, кто не знает, что внутри.

Эталонная реализация — пакет container/heap, и устроен он непривычно: это не тип, а набор функций над вашим типом. Вы храните срез сами и реализуете пять методов интерфейса heap.Interface: Len, Less, Swap из sort.Interface плюс Push и Pop, которые добавляют и снимают последний элемент среза. Всплытие и погружение делают heap.Push и heap.Pop пакета: ровно та двоичная куча, что описана выше, вплоть до формул по индексу. Куча получается минимальной по вашему Less: наверху элемент, который «меньше» всех. Нужен максимум — переворачивают Less.

Сложность предсказуемая: heap.Push и heap.Pop — O(log n), heap.Init превращает готовый срез в кучу за O(n), а посмотреть вершину не забирая — это просто h[0], O(1). Место срез берёт с запасом и расширяет сам обычным append.

Две операции, которых нет у кучи в Java, здесь есть: heap.Fix(h, i) чинит кучу после изменения приоритета элемента с индексом i за O(log n), а heap.Remove(h, i) удаляет произвольный элемент за O(log n). Условие одно: вы должны знать индекс. Поэтому в примере из документации у элемента есть поле index, которое Swap поддерживает при каждом обмене. Без индекса поиск элемента остаётся O(n), как и везде. Это снимает главную граблю Дейкстры, разобранную в статье про взвешенные графы: приоритет можно уменьшить на месте, а не дописывать дубликат.

Главная же грабля вот какая: срез под кучей не отсортирован. Цикл for range по нему выдаёт элементы в том порядке, в каком они лежат в массиве, где действует лишь слабая упорядоченность. Гарантирован только один элемент — тот, что в h[0]. Порядок появляется при выемке: элементы выходят через heap.Pop строго по возрастанию.

живой пример

package main

import (
	"container/heap"
	"fmt"
)

type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func main() {
	queue := &minHeap{5, 1, 9, 3}
	heap.Init(queue)
	fmt.Println(*queue)                           // [1 3 9 5] — не отсортировано
	fmt.Println((*queue)[0])                      // 1 — а вот это гарантия
	fmt.Println(heap.Pop(queue), heap.Pop(queue)) // 1 3 — по возрастанию
}

Кстати об Init: готовый срез он не перекладывает по одному элементу, а превращает в кучу целиком — та самая O(N) вместо O(N·log N).

Ещё две мелочи: методы Push и Pop вашего типа вызывать напрямую нельзя, они для пакета, всплытие и погружение делают только heap.Push и heap.Pop; а heap.Pop возвращает any, и на выходе нужно утверждение типа. Обобщённой кучи в стандартной библиотеке нет, поэтому в проектах часто заводят свою в двадцать строк на дженериках или берут пакет. Куча не потокобезопасна, как и любой срез: для нескольких горутин её закрывают мьютексом.

Кучу в JavaScript пишут руками чаще, чем в других языках, потому что в стандартной библиотеке её нет: ни приоритетной очереди, ни heapify. Устройство знать приходится и тем, кто берёт пакет: у готовой кучи есть поведение, которое удивляет всех, кто не знает, что внутри.

Реализации две. Самодельная — класс на двадцать строк над обычным массивом, как MinHeap в примере с топ-K выше: ровно та двоичная куча, что описана выше, вплоть до формул по индексу. Готовая — пакет, например heap-js или @datastructures-js/priority-queue; внутри у них тот же массив. И там и там по умолчанию куча минимальная по функции сравнения: наверху элемент, который «меньше». Нужен максимум — переворачивают сравнение.

Сложность предсказуемая: вставка и выемка вершины — O(log n), посмотреть вершину не забирая — O(1), это просто нулевая ячейка массива, а построить кучу из готового массива можно за O(n), если делать погружение от середины к началу, а не вставлять по одному. Массив растёт сам.

Две операции стоят дорого: «есть ли элемент» и «удалить произвольный элемент» — O(n). Куча не знает, где лежит конкретное значение, ей приходится просматривать весь массив. То же с изменением приоритета: поменять поле у объекта, который уже в куче, нельзя, куча об этом не узнает и сломает порядок. Это главная грабля Дейкстры, и как её обходят, дописывая новый элемент вместо правки старого, разбирает статья про взвешенные графы.

Соблазн обойтись без кучи в JavaScript особенно велик: array.push(x); array.sort(cmp) после каждой вставки выглядит проще. Это O(n·log n) на каждую операцию вместо O(log n), и на очереди из десятков тысяч событий разница между «мгновенно» и «секунды».

Главная же грабля вот какая: массив под кучей не отсортирован. Ни for...of, ни JSON.stringify, ни join не выдают элементы по возрастанию — они идут в том порядке, в каком лежат в массиве, где действует лишь слабая упорядоченность. Гарантирован только один элемент — тот, что на вершине. Порядок появляется при выемке: элементы выходят через pop строго по возрастанию.

живой пример

function siftDown(a, i, n) {
  while (2 * i + 1 < n) {
    let c = 2 * i + 1;
    if (c + 1 < n && a[c + 1] < a[c]) c++;
    if (a[i] <= a[c]) break;
    [a[i], a[c]] = [a[c], a[i]];
    i = c;
  }
}

function heapify(a) {
  for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i, a.length);
}

function pop(a) {
  const top = a[0];
  const last = a.pop();
  if (a.length > 0) {
    a[0] = last;
    siftDown(a, 0, a.length);
  }
  return top;
}

const queue = [5, 1, 9, 3];
heapify(queue);
console.log(queue);                  // [ 1, 3, 9, 5 ] — не отсортировано
console.log(queue[0]);               // 1 — а вот это гарантия
console.log(pop(queue), pop(queue)); // 1 3 — по возрастанию

Кстати о heapify в примере: готовый массив он не перекладывает по одному элементу, а превращает в кучу целиком — та самая O(N) вместо O(N·log N).

Ещё одна мелочь: в одном потоке гонок нет, и очередь задач на куче между таймерами и обработчиками безопасна без замков; между воркерами куча не разделяется.

Кучу почти никогда не пишут руками, но её устройство знать приходится: у готового модуля есть поведение, которое удивляет всех, кто не знает, что внутри.

Эталонная реализация — модуль heapq, и устроен он непривычно: это не класс, а набор функций над обычным списком. heappush и heappop делают всплытие и погружение прямо в вашем списке: ровно та двоичная куча, что описана выше, вплоть до формул по индексу. Разница с нашим примером одна — куча всегда минимальная: наверху наименьший элемент по естественному порядку. Компаратора нет вовсе. Нужен максимум — кладут элементы с минусом или кортежем (-priority, item); чтобы при равных приоритетах кортежи не сравнивали сами объекты, между ними ставят счётчик: (priority, next(counter), item).

Сложность предсказуемая: heappush и heappop — O(log n), heapify превращает готовый список в кучу за O(n), а посмотреть вершину не забирая — это просто heap[0], O(1). Две операции в одну: heapreplace снимает вершину и кладёт новый элемент одним погружением, heappushpop наоборот, и обе дешевле пары вызовов. А вопрос «топ-K» решён готовыми heapq.nlargest(k, iterable) и nsmallest, внутри у которых та самая куча размера K.

Две операции стоят дорого: x in heap и удаление произвольного элемента — O(n), это обычный список, и куча не знает, где лежит конкретное значение. Нет и операции «изменить приоритет элемента, который уже внутри»: поменять поле у объекта в куче нельзя, куча об этом не узнает и сломает порядок. Документация heapq советует помечать старую запись удалённой и класть новую, а при выемке пропускать помеченные; это главная грабля Дейкстры, разобранная в статье про взвешенные графы.

Главная же грабля вот какая: список под кучей не отсортирован. Ни for, ни print, ни срез не выдают элементы по возрастанию — они идут в том порядке, в каком лежат в списке, где действует лишь слабая упорядоченность. Гарантирован только один элемент — heap[0]. Порядок появляется при выемке: элементы выходят через heappop строго по возрастанию.

живой пример

import heapq

queue = [5, 1, 9, 3]
heapq.heapify(queue)
print(queue)                                       # [1, 3, 9, 5] — не отсортировано
print(queue[0])                                    # 1 — а вот это гарантия
print(heapq.heappop(queue), heapq.heappop(queue))  # 1 3 — по возрастанию

Кстати о heapify: готовый список он не перекладывает по одному элементу, а превращает в кучу целиком — та самая O(N) вместо O(N·log N). А sorted(heap) даёт отсортированную копию, не ломая кучу.

Ещё две мелочи: heapq не потокобезопасен, для нескольких потоков есть queue.PriorityQueue, обёртка над тем же heapq с замком; и класть в кучу несравнимые объекты нельзя, heappush упадёт с TypeError при первом же сравнении, отсюда и счётчик в кортеже.

• В PriorityQueue дёшевы peek, offer, poll; contains и remove(Object) — O(n), обход не отсортирован; изменить приоритет элемента внутри нельзя; конструктор от коллекции строит кучу за O(N).

• container/heap это функции над вашим типом с пятью методами; вершина в h[0], heap.Init за O(N), обход среза не отсортирован; heap.Fix и heap.Remove по индексу за O(log n) — здесь приоритет менять можно.

• Кучи в языке нет: класс на двадцать строк или пакет; sort после каждой вставки это O(n·log n) вместо O(log n); массив под кучей не отсортирован, гарантирована только вершина.

• heapq это функции над списком, куча только минимальная, максимум через минус; heapify за O(N), nlargest и nsmallest для топ-K, heapreplace дешевле пары вызовов; список не отсортирован, приоритет меняют пометкой старой записи.