Heap и heap sort
Накратко: Heap е почти пълно двоично дърво, записано в масив, в което най-големият (или най-малкият) елемент е винаги в корена; heap sort подрежда на място за O(n log n).
Проблем
Първите 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:
int[] heap = {58, 40, 25, 31, 12, 3, 7};for (int i = 0; 2 * i + 2 < heap.length; i++) { int left = 2 * i + 1, right = 2 * i + 2; System.out.println(heap[i] + " -> " + heap[left] + " " + heap[right]);}int child = 4;int parent = (child - 1) / 2;System.out.println("родителят на " + heap[child] + " (място " + child + ") е " + heap[parent] + " (място " + parent + ")");58 -> 40 2540 -> 31 1225 -> 3 7родителят на 12 (място 4) е 40 (място 1)58 е над 40 и 25, 40 е над 31 и 12, 25 е над 3 и 7. Всеки родител е по-голям от децата си, а 58 е най-голямото.
(child - 1) / 2 е деление на цели числа: 3 / 2 е 1, остатъкът отпада.Виж го
Потъване: как масивът става heap
Как масив в произволен ред става heap? С една операция: потъване (sift down). Елементът на място i се сравнява с двете си деца. Ако някое е по-голямо, сменят се местата с по-голямото, и елементът продължава надолу. Спира, когато е поне колкото децата си или когато деца няма.
Строенето пуска потъването за всеки родител, от последния към върха. Листата (долният ред) нямат деца: те са heap сами по себе си. Така, когато стигнеш до родител, двете поддървета под него вече са heap и той трябва само да потъне на мястото си.
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, 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; swap(a, i, big); i = big; }}Heap sort е строенето и още един цикъл. Максимумът е на място 0: сменя се с последния елемент и вече е на окончателното си място. Heap-ът се свива с едно, а новият връх потъва. Така n - 1 пъти:
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, end); }}int[] sales = {12, 40, 7, 31, 58, 3, 25};buildHeap(sales);System.out.println("Heap: " + Arrays.toString(sales));heapSort(sales);System.out.println("Подредено: " + Arrays.toString(sales));Heap: [58, 40, 25, 31, 12, 3, 7]Подредено: [3, 7, 12, 25, 31, 40, 58]static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, 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; swap(a, i, big); i = big; }}
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); 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 пъти.
Втори масив няма: размените са в самия масив. Това е подреждане на място.
Пробвай
Предвиди изхода
Строенето пуска потъването от последния родител към върха. Какво е в масива след него?
int[] sales = {5, 9, 2, 8};buildHeap(sales);System.out.println(Arrays.toString(sales));Пробвай
Попълни
Лявото дете на място i е:
int left = , right = 2 * i + 2;Децата на i са на 2i + 1 и 2i + 2. Върхът е на 0, затова децата му са на 1 и 2, а не на 0 и 1.
Идеята
Колко струва
- Потъване: на всяко ниво две сравнения и най-много една размяна. Дървото с 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 |
static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, 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; swap(a, i, big); i = big; }}
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); 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, но подреденото излиза разбъркано:
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, a.length); }}int[] sales = {12, 40, 7, 31, 58, 3, 25};heapSort(sales);System.out.println(Arrays.toString(sales));[58, 31, 40, 25, 12, 7, 3]На кой ред е грешката?
Избери реда с грешката.
Потъването получава целия масив, а не само heap-а. Максимумът, сложен в края, пак е „дете“ и изплува обратно нагоре. Границата е end: всичко от end нататък е вече подредено и потъването не бива да го вижда. С end изходът е [3, 7, 12, 25, 31, 40, 58].
Виж го
Първите 10 без да подреждаш всичко
Обратно към началната страница. Обърни идеята: пази min-heap с 10 елемента, най-малкият от тях отгоре. Той е „десетият“: прагът, над който трябва да е продуктът, за да влезе.
- Докато има по-малко от 10, всеки продукт влиза.
- После всеки нов се сравнява само с върха. Ако е по-голям, заема мястото на върха и потъва. Ако не е, отпада с едно сравнение.
PriorityQueue е точно такъв min-heap: peek() дава върха, poll() го вади, add() добавя и изплува.record Product(int id, int sold) {}
PriorityQueue<Product> best = new PriorityQueue<>(Comparator.comparingInt(Product::sold));for (int id = 1; id <= 1_000_000; id++) { Product p = new Product(id, (int) (id * 48271L % 1_000_003)); if (best.size() < 10) { best.add(p); } else if (p.sold() > best.peek().sold()) { best.poll(); best.add(p); }}List<Product> top = new ArrayList<>(best);top.sort(Comparator.comparingInt(Product::sold).reversed());for (Product p : top) { System.out.println("продукт " + 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 |
При милион продукта heap-ът прави 1 000 467 сравнения, а merge sort 18 674 993. Работата е O(n · log 10): heap-ът никога не става по-голям от 10, затова на продукт се пада почти точно едно сравнение.
По-точно, за любопитните
Heap, от който вадиш „най-важния“ и добавяш нови, е приоритетна опашка. Тя е отделна тема в модула „Структури от данни“: там е и изплуването нагоре, и защо задачите в планировчик, събитията в симулация и Dijkstra стоят върху нея.
PriorityQueue в Java е min-heap по естествения ред. За max-heap се дава Comparator.reverseOrder().Как е в другите езици: 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 ти трябва сега?
Тест