Heap и heap sort

Код на:JavaC#PythonJavaScript

Накратко: 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:

heap = [58, 40, 25, 31, 12, 3, 7]
i = 0
while 2 * i + 2 < len(heap):
    left, right = 2 * i + 1, 2 * i + 2
    print(f"{heap[i]} -> {heap[left]} {heap[right]}")
    i += 1
child = 4
parent = (child - 1) // 2
print(f"родителят на {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 е най-голямото.

// е целочисленото деление: 3 // 2 е 1. С / щеше да е 1.5 и индексът нямаше да става.

Виж го

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

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

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

def sift_down(a, i, n):
    while True:
        big = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and a[left] > a[big]:
            big = left
        if right < n and 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 пъти:

def build_heap(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))


def heap_sort(a):
    build_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)

sales = [12, 40, 7, 31, 58, 3, 25]
build_heap(sales)
print(f"Heap: {sales}")
heap_sort(sales)
print(f"Подредено: {sales}")

Изход

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

def sift_down(a, i, n):
    while True:
        big = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and a[left] > a[big]:
            big = left
        if right < n and a[right] > a[big]:
            big = right
        if big == i:
            return
        a[i], a[big] = a[big], a[i]
        i = big


def build_heap(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))


def heap_sort(a):
    build_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)

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

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

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

Пробвай

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

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

sales = [5, 9, 2, 8]
build_heap(sales)
print(sales)

Отговор

[9, 8, 2, 5]

[2, 5, 8, 9]

[9, 5, 2, 8]

Провери

Пробвай

Попълни

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

left, right = , 2 * i + 2

Провери

Идеята

Колко струва

• Потъване: на всяко ниво две сравнения и най-много една размяна. Дървото с 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 не пускаме, за да не замръзне страницата.

def sift_down(a, i, n):
    while True:
        big = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and a[left] > a[big]:
            big = left
        if right < n and a[right] > a[big]:
            big = right
        if big == i:
            return
        a[i], a[big] = a[big], a[i]
        i = big


def build_heap(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))


def heap_sort(a):
    build_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(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, но подреденото излиза разбъркано:

def heap_sort(a):
    build_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, len(a))

sales = [12, 40, 7, 31, 58, 3, 25]
heap_sort(sales)
print(sales)

Изход

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

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

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

1def heap_sort(a):2 build_heap(a)3 for end in range(len(a) - 1, 0, -1):4 a[0], a[end] = a[end], a[0]5 sift_down(a, 0, len(a))

Провери

Виж го

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

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

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

В Python heapq прави min-heap от обикновен списък: best[0] е върхът, heappush добавя, а heapreplace сменя върха и потъва.

import heapq

best = []
for product in range(1, 1_000_001):
    sold = product * 48271 % 1_000_003
    if len(best) < 10:
        heapq.heappush(best, (sold, product))
    elif sold > best[0][0]:
        heapq.heapreplace(best, (sold, product))

for sold, product in sorted(best, reverse=True):
    print(f"продукт {product}: {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 стоят върху нея.

heapq е само min-heap. За max-heap се пазят отрицателни числа. За тази точна задача има и готово: heapq.nlargest(10, …) прави същото отвътре.

Как е в другите езици: 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 на ръка. Препиши sift_down така, че родителят да е най-много колкото децата си. Подреди с него продажбите в обратен ред.
• Броене на сравненията. Добави брояч в потъването и пусни 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 и скача из паметта, а процесорът обича да чете подред

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Big-O: как расте работата · Най-добър, среден и най-лош случай · Merge sort и „разделяй и владей“ · Quick sort и лошият пивот
• Продължава в: Counting sort и radix sort · Стабилно сортиране и вграденият sort · Приоритетна опашка · Dijkstra
• Задачи по темата: Сортиране