Към съдържанието
wannacode

Приоритетна опашка

Накратко: Приоритетната опашка винаги дава най-важния елемент, например най-спешната поръчка; върху heap и добавянето, и вземането са O(log n), а в Java тя е PriorityQueue.

Проблем

Кой тръгва пръв

Диспечерът на доставките разпределя поръчки към куриерите. Всяка поръчка има краен срок: след колко минути трябва да е при клиента. Свободният куриер винаги получава най-спешната поръчка.

Поръчките идват непрекъснато. В петък вечер в голям град чакат по 10 000 наведнъж, а за деня минават 100 000.

Първото решение е списък, подреден по срок. При всяка нова поръчка тя се добавя и списъкът се подрежда наново. Подреждането е O(n log n) (виж merge sort), и то за всяка поръчка. Дори най-умното подреждане, което забелязва, че списъкът почти е подреден, трябва поне да мине през него: n стъпки при всяка нова поръчка.

А на куриера не му трябва целият ред. Трябва му само първата.

Идеята

Опашка, която знае само кой е пръв

Структура с две действия: добави поръчка и вземи най-спешната. Това е приоритетна опашка (priority queue). Не обещава ред за всички, а само кой е пръв.

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

  • Вземането вече го знаеш от heap sort. Върхът излиза, последният елемент отива на негово място и потъва надолу. Разликата е, че потъва към по-спешното дете.
  • Добавянето е новото: изплуване (sift up). Новата поръчка влиза в края на масива. После се сравнява с родителя си на място (i - 1) / 2. Ако е по-спешна, сменят се местата, и тя продължава нагоре. Спира, когато родителят е по-спешен или когато стигне върха.

Виж го

Изплуване и потъване

Добавянето: в края и нагоре.

void push(Order order) {
    items.add(order);
    int i = items.size() - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (!less(i, parent)) return;
        swap(i, parent);
        i = parent;
    }
}

Вземането: върхът излиза, последният застава на негово място и потъва.

Order poll() {
    Order top = items.get(0);
    items.set(0, items.get(items.size() - 1));
    items.remove(items.size() - 1);
    if (!items.isEmpty()) siftDown(0);
    return top;
}


private void siftDown(int i) {
    int n = items.size();
    while (true) {
        int low = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && less(left, low)) low = left;
        if (right < n && less(right, low)) low = right;
        if (low == i) return;
        swap(i, low);
        i = low;
    }
}

Шест поръчки чакат. Влиза нова с 18 минути, а куриерът взима най-спешната:

Order[] waiting = {
    new Order("A-101", 10),
    new Order("A-102", 15),
    new Order("A-103", 30),
    new Order("A-104", 20),
    new Order("A-105", 25),
    new Order("A-106", 40)
};
var queue = new DeadlineQueue();
for (Order o : waiting) queue.push(o);
System.out.println("Heap: " + queue.deadlines());
queue.push(new Order("A-107", 18));
System.out.println("След A-107: " + queue.deadlines());
Order next = queue.poll();
System.out.println("Куриерът взима " + next.id() + " (" + next.deadline() + " мин)");
System.out.println("Остават: " + queue.deadlines());
Изход
Heap: [10, 15, 30, 20, 25, 40]
След A-107: [10, 15, 18, 20, 25, 40, 30]
Куриерът взима A-101 (10 мин)
Остават: [15, 20, 18, 30, 25, 40]

class DeadlineQueue {
    private final List<Order> items = new ArrayList<>();


    void push(Order order) {
        items.add(order);
        int i = items.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (!less(i, parent)) return;
            swap(i, parent);
            i = parent;
        }
    }


    Order poll() {
        Order top = items.get(0);
        items.set(0, items.get(items.size() - 1));
        items.remove(items.size() - 1);
        if (!items.isEmpty()) siftDown(0);
        return top;
    }


    private void siftDown(int i) {
        int n = items.size();
        while (true) {
            int low = i;
            int left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && less(left, low)) low = left;
            if (right < n && less(right, low)) low = right;
            if (low == i) return;
            swap(i, low);
            i = low;
        }
    }


    private boolean less(int i, int j) {
        return items.get(i).deadline()
                < items.get(j).deadline();
    }


    private void swap(int i, int j) {
        Order tmp = items.get(i);
        items.set(i, items.get(j));
        items.set(j, tmp);
    }


    int size() {
        return items.size();
    }


    List<Integer> deadlines() {
        return items.stream()
                .map(Order::deadline).toList();
    }
}
Стъпка по стъпка, с думи
  1. Шест чакащи поръчки, сроковете са в минути. Min-heap: всеки родител е най-много колкото децата си, затова най-спешната, 10, е отгоре.
  2. push: нова поръчка с 18 минути влиза в края на масива, място 6. В дървото е дете на 30.
  3. Изплуване: родителят на 6 е (6 - 1) / 2 = 2. 18 е по-спешно от 30, разменят се.
  4. Родителят на 2 е 0, с 10 минути. 10 е по-спешно от 18: поръчката спира. Една размяна, най-много по една на ниво.
  5. poll: куриерът взима върха, поръчката с 10 минути. На място 0 остава дупка.
  6. Последният, 30, отива на върха и масивът се свива до шест. Сега siftDown го слага на мястото му.
  7. Потъване, както в heap sort, но към по-спешното дете: 30 срещу 15 и 18 се разменя с 15, после срещу 20 и 25 се разменя с 20.
  8. Място 3 няма деца: край. Отгоре е 15, следващата по спешност. И двете движения струват O(log n): височината на дървото.

Масивът не е подреден: 18 стои преди 20. Подредено е само това, което трябва: най-ранният срок е отгоре.

Пробвай

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

Пет поръчки влизат в празна опашка. Какво има в масива след това?

var queue = new DeadlineQueue();
queue.push(new Order("B-1", 40));
queue.push(new Order("B-2", 25));
queue.push(new Order("B-3", 30));
queue.push(new Order("B-4", 10));
queue.push(new Order("B-5", 35));
System.out.println(queue.deadlines());
Отговор

Пробвай

Попълни

Изплуването сравнява елемента на място i с родителя му. Къде е родителят?

int parent = ;

Идеята

Колко струва

  • Добавяне: най-много едно сравнение на ниво. Дървото с n елемента има около log₂ n нива: O(log n).
  • Вземане: две сравнения на ниво при потъването: също O(log n).
  • Кой е пръв: върхът е на място 0, без нито едно сравнение: O(1).

Пусни диспечера с двата варианта. Поръчките идват една по една, след всяка втора куриер взима най-спешната, а накрая куриерите взимат останалите. Броят се сравненията между два срока:

  • Подреден списък: подреждане след всяка поръчка O(n²)
  • Min-heap: изплуване и потъване O(n log n)
Алгоритъмn = 10n = 1000n = 10 000n = 100 000
Подреден списък: подреждане след всяка поръчка1163 4306 250 042≈ 625 004 200
Min-heap: изплуване и потъване2817 397256 8073 386 161
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class DeadlineQueue {
    private final List<Order> items = new ArrayList<>();


    void push(Order order) {
        items.add(order);
        int i = items.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (!less(i, parent)) return;
            swap(i, parent);
            i = parent;
        }
    }


    Order poll() {
        Order top = items.get(0);
        items.set(0, items.get(items.size() - 1));
        items.remove(items.size() - 1);
        if (!items.isEmpty()) siftDown(0);
        return top;
    }


    private void siftDown(int i) {
        int n = items.size();
        while (true) {
            int low = i;
            int left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && less(left, low)) low = left;
            if (right < n && less(right, low)) low = right;
            if (low == i) return;
            swap(i, low);
            i = low;
        }
    }


    private boolean less(int i, int j) {
        return items.get(i).deadline()
                < items.get(j).deadline();
    }


    private void swap(int i, int j) {
        Order tmp = items.get(i);
        items.set(i, items.get(j));
        items.set(j, tmp);
    }


    int size() {
        return items.size();
    }


    List<Integer> deadlines() {
        return items.stream()
                .map(Order::deadline).toList();
    }
}

При 10 поръчки подреденият списък прави 11 сравнения, а heap-ът 28: при малко поръчки списъкът е напълно добре. При 10 000 са 6 250 042 срещу 256 807. При 100 000 heap-ът прави 3 386 161, а списъкът около 625 милиона. Него Bench не го пуска, а го оценява по кривата.

Подреденият списък в Bench е в най-добрия си случай: новата поръчка само се плъзга до мястото си, без да се подрежда нищо друго. Пак е O(n) на поръчка, защото минава средно през половината списък. Heap-ът е O(log n) на поръчка.

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

Кое подреждане забелязва, че списъкът почти е подреден? TimSort, който ползват sort в Python, List.sort и Collections.sort в Java и Array.prototype.sort в JavaScript (виж вградения sort). Той намира подредената част с около n сравнения и вкарва новия елемент в нея: O(n) на поръчка. Bench брои още по-евтин вариант, плъзгането от края, и пак излиза O(n). C# List.Sort е introsort и не търси подредени части: при всяка поръчка прави около n log n сравнения, още повече.

Защо изплуването е бързо и на практика? Новата поръчка обикновено е някъде по средата по спешност. Половината елементи на heap са листа, четвъртината са точно над тях, и т.н. Затова средно случайна поръчка спира след едно-две нива. Най-лошият случай (новата е най-спешната от всички) пак е само log₂ n.

Пробвай

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

Колега е написал потъването, но куриерите понякога тръгват с по-късна поръчка преди по-ранна:

private void siftDown(int i) {
    int n = items.size();
    while (true) {
        int low = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && less(left, low)) low = left;
        if (right < n && less(right, i)) low = right;
        if (low == i) return;
        swap(i, low);
        i = low;
    }
}
var queue = new DeadlineQueue();
queue.push(new Order("C-1", 5));
queue.push(new Order("C-2", 10));
queue.push(new Order("C-3", 20));
queue.push(new Order("C-4", 30));
queue.push(new Order("C-5", 40));
queue.push(new Order("C-6", 50));
List<Integer> taken = new ArrayList<>();
while (queue.size() > 0) taken.add(queue.poll().deadline());
System.out.println(taken);
Изход
[5, 20, 10, 30, 40, 50]

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

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

Виж го

Готовите опашки на всеки език

В проект не пишеш heap сам. Почти всеки език има приоритетна опашка, и всяка си има особеност.

PriorityQueue в Java е min-heap. Редът идва от Comparator: тук по срока. add изплува, poll вади върха, peek го показва, без да го вади.

Особеността: обхождането с for върви по масива на heap-а, не по ред. Същото е при toString() и при stream(). По ред вади само poll.

var queue = new PriorityQueue<Order>(
        Comparator.comparingInt(Order::deadline));
queue.add(new Order("A-101", 30));
queue.add(new Order("A-102", 10));
queue.add(new Order("A-103", 20));
queue.add(new Order("A-104", 25));
System.out.println("Най-спешна: " + queue.peek().id());
System.out.print("Отвътре:");
for (Order o : queue) System.out.print(" " + o.deadline());
System.out.println();
while (!queue.isEmpty()) {
    Order o = queue.poll();
    System.out.println(o.id() + " (" + o.deadline() + " мин)");
}
Изход
Най-спешна: A-102
Отвътре: 10 25 20 30
A-102 (10 мин)
A-103 (20 мин)
A-104 (25 мин)
A-101 (30 мин)
По-точно, за любопитните

Нито една от тези опашки не е стабилна: две поръчки с еднакъв срок може да излязат в какъвто и да е ред (виж стабилността). Ако редът на идване е важен, сложи пореден номер, както в Python отгоре.

Смяна на срока на поръчка, която вече чака, няма в нито една от трите. remove в Java търси елемента линейно: O(n). Обичайното решение е да добавиш поръчката пак с новия срок, а старото копие да прескочиш, когато излезе. Така работи и Dijkstra в модула за графи (algo-graphs), който предстои.

Как е в другите езици: Java има PriorityQueue, C# PriorityQueue<TElement, TPriority> (от .NET 6), Python heapq (функции върху списък), а JavaScript няма вградена приоритетна опашка.

Виж го

Още две задачи за heap

Първите k. Кои 10 продукта се продават най-много от милион? Min-heap, който никога няма повече от 10 елемента: всеки нов се сравнява с върха. Това е в урока за heap, там е и Bench.

Сливане на k подредени списъка. Три склада пращат поръчките си, подредени по срок. Трябва един общ маршрут, пак по срок. В heap-а стои само началото на всеки списък. Вадиш най-ранното, а на негово място слагаш следващото от същия склад:

int[][] lists = {{5, 20, 45}, {10, 15, 50}, {12, 30}};
String[] names = {"Север", "Юг", "Център"};
var heads = new PriorityQueue<Head>(
        Comparator.comparingInt(Head::deadline));
for (int k = 0; k < lists.length; k++) {
    heads.add(new Head(lists[k][0], k, 0));
}
List<String> route = new ArrayList<>();
while (!heads.isEmpty()) {
    Head h = heads.poll();
    route.add(h.deadline() + " " + names[h.list()]);
    int next = h.index() + 1;
    if (next < lists[h.list()].length) {
        heads.add(new Head(lists[h.list()][next], h.list(), next));
    }
}
System.out.println("Маршрут: " + String.join(", ", route));
Изход
Маршрут: 5 Север, 10 Юг, 12 Център, 15 Юг, 20 Север, 30 Център, 45 Север, 50 Юг

Heap-ът никога няма повече от k елемента (тук 3). Затова N поръчки струват O(N log k), а не O(N log N) за подреждане на всичко. Така се сливат и подредени части от файл, който не се събира в паметта.

По-точно, за любопитните
Python има готово сливане: heapq.merge. В Java, C# и JavaScript то се пише като тук.

Merge sort също слива подредени части, но по две (merge sort). С heap се сливат k наведнъж.

Упражнение

Честна опашка

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

Еднакъв срок, първа е по-ранната. Направи опашка FairQueue, в която при еднакъв срок първа излиза поръчката, която е дошла по-рано. Пази пореден номер с всяка поръчка и сравнявай първо по срок, после по номер. Пусни я с поръчките A-1 (30), A-2 (20), A-3 (30), A-4 (20), A-5 (10), A-6 (20), в този ред:

Изход
Ред: A-5, A-2, A-4, A-6, A-1, A-3

Още задачи

  • Max-heap. Обърни сравнението и направи опашка, която дава най-скъпата поръчка първа.
  • Брой сравненията. Добави брояч в изплуването и потъването и пусни 1000 случайни поръчки. Колко сравнения се падат на поръчка?
  • Първите три. Как да вземеш трите най-спешни поръчки, без да вадиш другите от опашката?

Тест

Провери се

1. Какво обещава приоритетната опашка?
2. Новата поръчка влиза в heap с 1 000 000 поръчки. Колко сравнения прави изплуването най-много?
3. В Python пазиш поръчките като (срок, речник) в heapq. Две поръчки имат еднакъв срок. Какво става?
4. Три склада пращат подредени по срок списъци, общо N поръчки. Как ги сливаш в един маршрут?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·