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

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

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

Проблем

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

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

Поръчките идват непрекъснато. В петък вечер в голям град чакат по 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. Ако е по-спешна, сменят се местата, и тя продължава нагоре. Спира, когато родителят е по-спешен или когато стигне върха.

Виж го

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

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

push(order) {
  this.#items.push(order);
  let i = this.#items.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (!this.#less(i, parent)) return;
    this.#swap(i, parent);
    i = parent;
  }
}

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

poll() {
  const items = this.#items;
  const top = items[0];
  items[0] = items[items.length - 1];
  items.pop();
  if (items.length > 0) this.#siftDown(0);
  return top;
}


#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, low)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}
#items и #siftDown са частни: отвън се виждат само push, poll и size.

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

const waiting = [
  { id: "A-101", deadline: 10 },
  { id: "A-102", deadline: 15 },
  { id: "A-103", deadline: 30 },
  { id: "A-104", deadline: 20 },
  { id: "A-105", deadline: 25 },
  { id: "A-106", deadline: 40 },
];
const queue = new DeadlineQueue();
for (const o of waiting) queue.push(o);
console.log(`Heap: ${queue.deadlines()}`);
queue.push({ id: "A-107", deadline: 18 });
console.log(`След A-107: ${queue.deadlines()}`);
const next = queue.poll();
console.log(`Куриерът взима ${next.id} (${next.deadline} мин)`);
console.log(`Остават: ${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 {
  #items = [];


  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }


  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }


  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }


  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }


  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }


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


  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}
Стъпка по стъпка, с думи
  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. Подредено е само това, което трябва: най-ранният срок е отгоре.

Пробвай

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

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

const queue = new DeadlineQueue();
queue.push({ id: "B-1", deadline: 40 });
queue.push({ id: "B-2", deadline: 25 });
queue.push({ id: "B-3", deadline: 30 });
queue.push({ id: "B-4", deadline: 10 });
queue.push({ id: "B-5", deadline: 35 });
console.log(queue.deadlines());
Отговор

Пробвай

Попълни

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

const 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 {
  #items = [];


  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }


  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }


  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }


  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }


  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }


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


  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}

При 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.

Пробвай

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

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

#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, i)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}
const queue = new DeadlineQueue();
queue.push({ id: "C-1", deadline: 5 });
queue.push({ id: "C-2", deadline: 10 });
queue.push({ id: "C-3", deadline: 20 });
queue.push({ id: "C-4", deadline: 30 });
queue.push({ id: "C-5", deadline: 40 });
queue.push({ id: "C-6", deadline: 50 });
const taken = [];
while (queue.size > 0) taken.push(queue.poll().deadline);
console.log(`[${taken.join(", ")}]`);
Изход
[5, 20, 10, 30, 40, 50]

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

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

Виж го

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

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

JavaScript няма вградена приоритетна опашка. Затова се ползва нашата DeadlineQueue от по-горе. В проект се ползва готов пакет от npm или такъв кратък клас.

const queue = new DeadlineQueue();
queue.push({ id: "A-101", deadline: 30 });
queue.push({ id: "A-102", deadline: 10 });
queue.push({ id: "A-103", deadline: 20 });
queue.push({ id: "A-104", deadline: 25 });
console.log(`Отвътре: ${queue.deadlines()}`);
while (queue.size > 0) {
  const o = queue.poll();
  console.log(`${o.id} (${o.deadline} мин)`);
}
Изход
Отвътре: [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-а стои само началото на всеки списък. Вадиш най-ранното, а на негово място слагаш следващото от същия склад:

В JavaScript това пак е нашата DeadlineQueue: тя сравнява само deadline, затова приема и обекти, които помнят склада и мястото.
const lists = [[5, 20, 45], [10, 15, 50], [12, 30]];
const names = ["Север", "Юг", "Център"];
const heads = new DeadlineQueue();
lists.forEach((list, k) => heads.push({ deadline: list[0], list: k, index: 0 }));
const route = [];
while (heads.size > 0) {
  const h = heads.poll();
  route.push(`${h.deadline} ${names[h.list]}`);
  const next = h.index + 1;
  if (next < lists[h.list].length) {
    heads.push({ deadline: lists[h.list][next], list: h.list, index: next });
  }
}
console.log(`Маршрут: ${route.join(", ")}`);
Изход
Маршрут: 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 за достъпно обучение по програмиране ·