Heap и heap sort в JavaScript

Проблем

Първите 10 от един милион

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

Първото, което ти идва наум, е да подредиш всички и да вземеш първите 10. Merge sort прави около 18,7 милиона сравнения за милион продукта (виж merge sort). От тях ти трябват 10 реда. Останалите 999 990 продукта се подреждат напразно.

Има и втора болка. Quick sort подрежда на място, но с лош пивот пада до O(n²) (виж quick sort). Merge sort е O(n log n) винаги, но иска втори масив колкото първия. Може ли и двете: на място и O(n log n) винаги?

Идеята

Heap: дърво, записано в масив

И за двете трябва структура, която знае само едно: кой е най-големият. Не е нужно всичко да е подредено.

Нарисувай масива като дърво. Мястото 0 е върхът. Под всяко място i има две деца:

лявото дете е на 2i + 1;
дясното дете е на 2i + 2;
родителят на място i е на (i - 1) / 2, с целочислено деление.

Указатели няма. Дървото е само начин да гледаш масива.

Масивът е heap (по-точно max-heap), когато всеки родител е поне колкото децата си. Тогава най-голямото е винаги на място 0. Подредено е само това: братята помежду си може да са в какъвто и да е ред.

Виж го

Децата и родителят по индекс

Heap от седем продажби. Програмата минава по родителите и печата децата им, после намира родителя на място 4:

const heap = [58, 40, 25, 31, 12, 3, 7];
for (let i = 0; 2 * i + 2 < heap.length; i++) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  console.log(`${heap[i]} -> ${heap[left]} ${heap[right]}`);
}
const child = 4;
const parent = Math.floor((child - 1) / 2);
console.log(`родителят на ${heap[child]} (място ${child}) е ${heap[parent]} (място ${parent})`);

58 -> 40 25
40 -> 31 12
25 -> 3 7
родителят на 12 (място 4) е 40 (място 1)

58 е над 40 и 25, 40 е над 31 и 12, 25 е над 3 и 7. Всеки родител е по-голям от децата си, а 58 е най-голямото.

В JavaScript / винаги дава дробно число: 3 / 2 е 1.5. Затова индексът е Math.floor((child - 1) / 2).

Виж го

Потъване: как масивът става heap

Как масив в произволен ред става heap? С една операция: потъване (sift down). Елементът на място i се сравнява с двете си деца. Ако някое е по-голямо, сменят се местата с по-голямото, и елементът продължава надолу. Спира, когато е поне колкото децата си или когато деца няма.

Строенето пуска потъването за всеки родител, от последния към върха. Листата (долният ред) нямат деца: те са heap сами по себе си. Така, когато стигнеш до родител, двете поддървета под него вече са heap и той трябва само да потъне на мястото си.

function siftDown(a, i, n) {
  while (true) {
    let big = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && a[left] > a[big]) big = left;
    if (right < n && a[right] > a[big]) big = right;
    if (big === i) return;
    [a[i], a[big]] = [a[big], a[i]];
    i = big;
  }
}

Heap sort е строенето и още един цикъл. Максимумът е на място 0: сменя се с последния елемент и вече е на окончателното си място. Heap-ът се свива с едно, а новият връх потъва. Така n - 1 пъти:

function buildHeap(a) {
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(a, i, n);
  }
}

function heapSort(a) {
  buildHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
}

const sales = [12, 40, 7, 31, 58, 3, 25];
buildHeap(sales);
console.log(`Heap: [${sales.join(", ")}]`);
heapSort(sales);
console.log(`Подредено: [${sales.join(", ")}]`);

Heap: [58, 40, 25, 31, 12, 3, 7]
Подредено: [3, 7, 12, 25, 31, 40, 58]

function siftDown(a, i, n) {
  while (true) {
    let big = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && a[left] > a[big]) big = left;
    if (right < n && a[right] > a[big]) big = right;
    if (big === i) return;
    [a[i], a[big]] = [a[big], a[i]];
    i = big;
  }
}

function buildHeap(a) {
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(a, i, n);
  }
}

function heapSort(a) {
  buildHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
}

Стъпка по стъпка, с думи

Седем продажби в масив. Същият масив е дърво: децата на място i са на 2i + 1 и 2i + 2.
Строенето почва от последния родител, място 2. siftDown: 7 е по-малко от детето си 25, разменят се.
Място 1: 40 срещу 31 и 58. По-голямото дете е 58: размяна.
Коренът: 12 се разменя с 58 и продължава да потъва. Едно ниво надолу 40 е по-голямо: още една размяна.
Heap: всеки родител е поне колкото децата си. Максимумът, 58, е на място 0.
Heap sort: максимумът се разменя с последния. 58 е на окончателното си място, а heap-ът се свива до шест.
Новият връх, 7, потъва: размяна с 40, после с 31. Отгоре вече е 40, следващият максимум. Така n - 1 пъти.

Втори масив няма: размените са в самия масив. Това е подреждане на място.

Пробвай

Предвиди изхода

Строенето пуска потъването от последния родител към върха. Какво е в масива след него?

const sales = [5, 9, 2, 8];
buildHeap(sales);
console.log(`[${sales.join(", ")}]`);

Отговор

[9, 8, 2, 5]

[2, 5, 8, 9]

[9, 5, 2, 8]

Пробвай

Попълни

Лявото дете на място i е:

const left = ;

Идеята

Колко струва

Потъване: на всяко ниво две сравнения и най-много една размяна. Дървото с n елемента има около log₂ n нива, затова потъването е O(log n).
Строене: изглежда като n потъвания по log n, но е O(n). Половината елементи са листа и не потъват изобщо, четвъртината слизат най-много с едно ниво, осмината с две… Сборът е под 2n.
Heap sort: строене плюс n - 1 потъвания от върха: O(n log n) във всеки случай. Лош вход, както лош пивот при quick sort, няма.

Пусни го срещу merge sort. И двата броят сравненията:

Heap sort O(n log n)
Подреждане (merge sort) O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Heap sort	38	16 807	3 019 656
Подреждане (merge sort)	21	8709	1 536 371

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function siftDown(a, i, n) {
  while (true) {
    let big = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && a[left] > a[big]) big = left;
    if (right < n && a[right] > a[big]) big = right;
    if (big === i) return;
    [a[i], a[big]] = [a[big], a[i]];
    i = big;
  }
}

function buildHeap(a) {
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(a, i, n);
  }
}

function heapSort(a) {
  buildHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
}

Двете криви растат еднакво, но heap sort прави около два пъти повече сравнения: при 100 000 продажби 3 019 656 срещу 1 536 371. Всяко потъване от върха слиза почти до дъното, защото там е поставен малък елемент.

Има и второ, което броят не показва: паметта. От място i потъването скача на 2i + 1. При голям масив това е далеч, и процесорът всеки път чака да дойде друго парче памет. Merge sort и quick sort четат подред, а процесорът е бърз точно тогава. Затова на практика heap sort е по-бавен, въпреки че обещава O(n log n) винаги.

По-точно, за любопитните

Защо вграденият sort не е heap sort? Заради горното. Heap sort е резервата: в C# Array.Sort е introsort, който почва с quick sort и минава на heap sort, ако разделянето стане твърде дълбоко. Така пази O(n log n), без да плаща цената на heap sort всеки път. Heap sort не е и стабилен: два продукта с еднакви продажби може да си сменят реда. Какво значи това, е в урока за стабилността.

Защо строенето е O(n): на височина h от дъното има около n / 2ʰ⁺¹ елемента и всеки слиза най-много h нива. Сборът n · (1/4 + 2/8 + 3/16 + …) е n · 1 = n.

Пробвай

Намери грешката

Някой е написал heap sort, но подреденото излиза разбъркано:

function heapSort(a) {
  buildHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, a.length);
  }
}

const sales = [12, 40, 7, 31, 58, 3, 25];
heapSort(sales);
console.log(`[${sales.join(", ")}]`);

[58, 31, 40, 25, 12, 7, 3]

На кой ред е грешката?

Избери реда с грешката.

Виж го

Първите 10 без да подреждаш всичко

Обратно към началната страница. Обърни идеята: пази min-heap с 10 елемента, най-малкият от тях отгоре. Той е „десетият“: прагът, над който трябва да е продуктът, за да влезе.

Докато има по-малко от 10, всеки продукт влиза.
После всеки нов се сравнява само с върха. Ако е по-голям, заема мястото на върха и потъва. Ако не е, отпада с едно сравнение.

JavaScript няма вграден heap. Затова тук е малък клас MinHeap със същите две движения: изплуване при push и потъване при replaceTop. Сравнява по sold:

class MinHeap {
  constructor() {
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(item) {
    const a = this.items;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (a[parent].sold <= a[i].sold) return;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  replaceTop(item) {
    const a = this.items;
    a[0] = item;
    let i = 0;
    while (true) {
      let small = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < a.length && a[left].sold < a[small].sold) small = left;
      if (right < a.length && a[right].sold < a[small].sold) small = right;
      if (small === i) return;
      [a[i], a[small]] = [a[small], a[i]];
      i = small;
    }
  }
}

const best = new MinHeap();
for (let id = 1; id <= 1_000_000; id++) {
  const sold = (id * 48271) % 1_000_003;
  if (best.size < 10) {
    best.push({ id, sold });
  } else if (sold > best.peek().sold) {
    best.replaceTop({ id, sold });
  }
}
const top = [...best.items].sort((a, b) => b.sold - a.sold);
for (const p of top) {
  console.log(`продукт ${p.id}: ${p.sold} продажби`);
}

продукт 188706: 1000002 продажби
продукт 377412: 1000001 продажби
продукт 566118: 1000000 продажби
продукт 754824: 999999 продажби
продукт 943530: 999998 продажби
продукт 132233: 999997 продажби
продукт 320939: 999996 продажби
продукт 509645: 999995 продажби
продукт 698351: 999994 продажби
продукт 887057: 999993 продажби

Пусни го срещу подреждането на всичко, до един милион:

Първите 10 с heap O(n)
Подреждане (merge sort) O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 1 000 000
Първите 10 с heap	15	1177	100 410	1 000 467
Подреждане (merge sort)	21	8709	1 536 371	18 674 993

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При милион продукта heap-ът прави 1 000 467 сравнения, а merge sort 18 674 993. Работата е O(n · log 10): heap-ът никога не става по-голям от 10, затова на продукт се пада почти точно едно сравнение.

По-точно, за любопитните

Heap, от който вадиш „най-важния“ и добавяш нови, е приоритетна опашка. Тя е отделна тема в модула „Структури от данни“: там е и изплуването нагоре, и защо задачите в планировчик, събитията в симулация и Dijkstra стоят върху нея.

Ако в проект ти трябва приоритетна опашка, има готови пакети в npm. В урока е написана на ръка, защото е къса и показва механизма.

Как е в другите езици: Java има PriorityQueue, C# PriorityQueue<TElement, TPriority>, Python heapq, а JavaScript няма вграден heap.

Упражнение

Първите три

Реши задачата в редактора си.

Първите три по продажби. Продажбите на дванайсет продукта са 12, 40, 7, 31, 58, 3, 25, 44, 19, 36, 50, 8. Намери трите най-големи с min-heap, който никога няма повече от три елемента, и ги отпечатай от най-голямото.

Първите три: [58, 50, 44]

Още задачи

Min-heap на ръка. Препиши siftDown така, че родителят да е най-много колкото децата си. Подреди с него продажбите в обратен ред.
Броене на сравненията. Добави брояч в потъването и пусни heap sort върху 7, 1000 и 100 000 продажби. Расте ли като n log n?
Последните 10. Кои 10 продукта се продават най-слабо? Какъв heap ти трябва сега?

Тест

Провери се

1. Heap е записан в масив. Върхът е на място 0. Къде са децата на място 3?На 6 и 7На 4 и 5На 7 и 8

2. Какво гарантира max-heap?Лявото дете е по-малко от дяснотоВсеки родител е поне колкото децата си, затова максимумът е на място 0Масивът е подреден

3. Трябват ти първите 10 по продажби от милион продукта. Кое прави най-малко работа?Пазиш min-heap с 10 елемента и всеки нов сравняваш с върха муДесет пъти търсиш максимума в целия списъкПодреждаш всичките и взимаш първите 10

4. Heap sort е O(n log n) винаги и не иска допълнителна памет. Защо вграденият sort не е heap sort?Защото работи само с цели числаЗащото е O(n²) в най-лошия случайПрави около два пъти повече сравнения от merge sort и скача из паметта, а процесорът обича да чете подред

Heap и heap sort

Бисквитки