Heap និង Priority Queue

មាតិកា

1. តើនរណាទៅបន្ទាប់?
2. គំនិតរបស់ Priority Queue
3. ហេតុអ្វីមិនគ្រាន់តែ Sort?
4. Binary Heap
5. Tree នៅក្នុង Array
6. Push និង Sift Up
7. Pop និង Sift Down
8. ការសាងសង់ PriorityQueue
9. Heap Sort និង Top-K
10. បញ្ហាពិត៖ Scheduler, Median, Merge
11. រូបមន្ត៖ priority-queue.ts សម្រាប់ algolab
12. សាកល្បងដោយខ្លួនឯង

1. តើនរណាទៅបន្ទាប់?

Queue ធម្មតាបម្រើមនុស្សតាមលំដាប់ដែលពួកគេមកដល់។ នោះគឺយុត្តិធម៌ ប៉ុន្តែពេលខ្លះវាជាច្បាប់ខុស៖

• មន្ទីរពេទ្យព្យាបាលអ្នកជំងឺដែលជើងបាក់មុនអ្នកដែលឈឺបំពង់កបន្តិច ទោះបីអ្នកឈឺបំពង់កមកដល់មុនក៏ដោយ។
• Payment server គួរតែបង់ប្រាក់តាមកាតមុននឹង resize រូបភាព profile។
• ប្រព័ន្ធ app ផែនទីចង់បានផ្លូវដែលមាន តម្លៃសរុបទាបបំផុត បន្ទាប់ មិនមែនផ្លូវដែលវារកឃើញមុនទេ។
• ប្រព័ន្ធប្រតិបត្តិការផ្តល់ CPU ដល់ process បន្ទាន់មុន process ផ្ទៃខាងក្រោយ។

ក្នុងគ្រប់ករណី ធាតុរង់ចាំក្នុងជួរ ប៉ុន្តែធាតុបន្ទាប់ដែលចេញត្រូវបានជ្រើសរើសតាម អាទិភាព មិនមែនតាមពេលវេលាមកដល់ទេ។ រចនាសម្ព័ន្ធសម្រាប់រឿងនេះគឺ priority queue ហើយវិធីឆ្លាតដើម្បីសាងសង់វាគឺ binary heap។ វាជាម៉ាស៊ីនដែលនៅពីក្រោយ task scheduler, បញ្ជី "top 10", ការក្លែងធ្វើព្រឹត្តិការណ៍ និងក្បួនដោះស្រាយផ្លូវខ្លីបំផុត (Dijkstra) ដែលអ្នកនឹងជួបក្នុងជំពូកបន្ទាប់។

2. គំនិតរបស់ Priority Queue

Priority queue គឺជា abstract data type៖ វាប្រាប់ថាអ្នកអាចធ្វើអ្វីបាន មិនមែនថាវាត្រូវបានសាងសង់យ៉ាងដូចម្តេចទេ។ វាមានប្រតិបត្តិការទាំងនេះ៖

ក្នុងជំពូកនេះ "អាទិភាពខ្ពស់បំផុត" មានន័យថា "រៀបចំមុនគេ"។ នោះធ្វើឲ្យវាជា min-priority queue៖ value តូចបំផុតចេញមុន ដូច្នេះការងារដែលមានអាទិភាព 1 យកឈ្នះការងារដែលមានអាទិភាព 5។ ដើម្បីបានកំណែ max ត្រូវបញ្ច្រាសការប្រៀបធៀប (យើងនឹងធ្វើវាដោយ comparator ដូចជា Array.sort)។

JavaScript មិនមាន priority queue ក្នុងខ្លួនទេ។ នោះធ្វើឲ្យមនុស្សភ្ញាក់ផ្អើល ព្រោះវាមាន Array, Map និង Set។ ភាសាផ្សេងៗជាច្រើនមានវាស្រាប់ (PriorityQueue របស់ Java, heapq របស់ Python, priority_queue របស់ C++) ហើយក្នុងការសម្ភាសន៍ ជាធម្មតាគេរំពឹងថាអ្នកនិយាយថា "ខ្ញុំនឹងប្រើ heap នៅទីនេះ" ឬសរសេរមួយតូចដោយខ្លួនឯង។ ដូច្នេះយើងនឹងធ្វើវា។

3. ហេតុអ្វីមិនគ្រាន់តែ Sort?

គំនិតសាមញ្ញពីរចូលមកក្នុងចិត្តមុនគេ។ ទាំងពីរយឺតជាងអ្វីដែលចាំបាច់។

គំនិត A៖ រក្សា array ដែលមិនបានរៀបចំ។ push គឺ O(1) ប៉ុន្តែ pop ត្រូវស្កេនគ្រប់ធាតុដើម្បីរកធាតុតូចបំផុត ដែលជា O(n)។

គំនិត B៖ រក្សា array ដែលបានរៀបចំ។ pop គឺ O(1) ប្រសិនបើធាតុតូចបំផុតនៅចុង ប៉ុន្តែរាល់ push ត្រូវរកកន្លែងរបស់វា ហើយរុញធាតុផ្សេងទៀត ដូច្នេះវាគឺ O(n) (ចាំថា ពីជំពូក Array និង String ការបញ្ចូលនៅកណ្តាល array រុញអ្វីៗទាំងអស់ដែលនៅពីក្រោយវា)។

ទោះបីជាវិធីណាក៏ដោយ ប្រតិបត្តិការមួយក្នុងចំណោមពីរមានតម្លៃ O(n)។ ប្រសិនបើអ្នកធ្វើ push n ដង និង pop n ដង សរុបគឺ O(n²)។ សម្រាប់ការងារ 100,000 នោះគឺ ដប់ពាន់លានជំហាន។ Heap បន្ថយប្រតិបត្តិការ ទាំងពីរ ទៅ O(log n)៖

សម្រាប់ធាតុ 100,000 log₂ n គឺប្រហែល 17។ Heap ធ្វើប្រហែល 17 ជំហានក្នុងមួយប្រតិបត្តិការ ខណៈដែល array ធ្វើរាប់ម៉ឺន។ ប្រសិនបើអ្នកត្រូវការរំលឹកថាហេតុអ្វី log n តូចខ្លាំងម្ល៉េះ សូមមើល ជំពូក Big-O ក្នុង Math for Programmers។

4. Binary Heap

Binary heap គឺជា binary tree (node នីមួយៗមាន child យ៉ាងច្រើនពីរ ដូចក្នុងជំពូកមុន) ដែលមានច្បាប់ពីរ៖

1. ច្បាប់រូបរាង៖ tree គឺ complete។ រាល់ level ពេញ លើកលែងតែ level ចុងក្រោយអាចមិនពេញ ហើយ level ចុងក្រោយត្រូវបានបំពេញពីឆ្វេងទៅស្តាំដោយគ្មានចន្លោះ។
2. ច្បាប់ heap (សម្រាប់ min-heap)៖ រាល់ node តូចជាង ឬស្មើនឹង child របស់វា។

          1
        /   \
       3     2
      / \   /
     5   9 8

ពិនិត្យច្បាប់ heap៖ 1 <= 3 និង 1 <= 2។ បន្ទាប់មក 3 <= 5 និង 3 <= 9។ បន្ទាប់មក 2 <= 8។ វាត្រឹមត្រូវគ្រប់ទីកន្លែង។ Value តូចបំផុតតែងតែនៅ root ដូច្នេះ peek() គឺគ្រាន់តែ "មើលនៅកំពូល"។

សូមប្រយ័ត្នកុំច្រឡំវាជាមួយ binary search tree ពីជំពូកចុងក្រោយ។ BST រៀបចំ ឆ្វេងទល់នឹងស្តាំ៖ ឆ្វេងតូចជាង ស្តាំធំជាង។ Heap រៀបចំ parent ទល់នឹង child៖ parent តូចជាង child ទាំងពីរ ហើយឆ្វេង និងស្តាំគ្មានលំដាប់រវាងគ្នាទេ (ក្នុងរូប 3 នៅខាងឆ្វេងនៃ 2 ហើយនោះមិនអីទេ)។ Heap តឹងរ៉ឹងតិចជាងច្រើន ហើយនោះជាមូលហេតុពិតប្រាកដដែលវាថោកជាងក្នុងការរក្សាឲ្យត្រឹមត្រូវ។ វាសន្យាតែរឿងមួយប៉ុណ្ណោះ៖ ធាតុតូចបំផុតនៅលើកំពូល។

ច្បាប់រូបរាងផ្តល់អំណោយមួយដល់យើង៖ ដោយសារ tree តែងតែ complete កម្ពស់របស់វាតែងតែប្រហែល log₂ n។ Heap មិនអាចថយចុះទៅជាបន្ទាត់វែងស្គមដូច BST ដែលគ្មានតុល្យភាពបានទេ។ តម្លៃដែលត្រូវបង់គឺអ្នកមិនអាចស្វែងរកនៅខាងក្នុងវាបានទេ។ Heap ពូកែតែរឿងមួយប៉ុណ្ណោះ ហើយវាធ្វើវាបានល្អ៖ "ផ្តល់ធាតុតូចបំផុតបន្ទាប់ឲ្យខ្ញុំ"។

5. Tree នៅក្នុង Array

ដោយសារ tree គឺ complete (គ្មានចន្លោះ) យើងមិនត្រូវការ node object និង pointer ទាល់តែសោះ។ យើងអាចរក្សាទុកវាក្នុង array ធម្មតា ដោយអាន tree ម្តងមួយជួរពីឆ្វេងទៅស្តាំ៖

tree:       1               array:  index:  0  1  2  3  4  5
          /   \                     value: [1, 3, 2, 5, 9, 8]
         3     2
        / \   /
       5   9 8

ទំនាក់ទំនងគ្រួសារក្លាយជានព្វន្តសាមញ្ញលើ index i៖

សាកល្បងជាមួយ array ខាងលើ។ Index 1 (value 3) មាន child នៅ 2*1+1 = 3 (value 5) និង 2*1+2 = 4 (value 9)។ ត្រូវ។ Parent របស់ index 5 (value 8) គឺ Math.floor((5-1)/2) = 2 (value 2)។ ត្រូវម្តងទៀត។

នេះគឺជាល្បិចដ៏ល្អ។ គ្មាន node គ្មាន field left/right គ្មាន pointer ហើយទិន្នន័យត្រូវបានវេចខ្ចប់ជាមួយគ្នាក្នុងអង្គចងចាំ ដែលមិត្តភាពនឹង CPU cache (មូលហេតុដូចគ្នាដែល array យកឈ្នះ linked list ក្នុងការអនុវត្តជាក់ស្តែង)។ វាក៏ជាការនឹករឭកដ៏ល្អអំពីគំនិតនព្វន្ត modular ថាលេខអាចត្រូវបានប្រើជាអាសយដ្ឋាន។

6. Push និង Sift Up

ដើម្បីបន្ថែម value យើងត្រូវរក្សាច្បាប់ទាំងពីរឲ្យពិត។ ច្បាប់រូបរាងនិយាយថា ធាតុថ្មីត្រូវទៅ កន្លែងទំនេរបន្ទាប់ ដែលគ្រាន់តែជាចុងនៃ array។ នោះអាចបំបែកច្បាប់ heap ប្រសិនបើធាតុថ្មីតូចជាង parent របស់វា។ ដូច្នេះយើងជួសជុលវាដោយ sift up៖ ខណៈដែលធាតុតូចជាង parent របស់វា ត្រូវប្តូរពួកវា។

តោះ push 5, 3, 8, 1, 9, 2 ម្តងមួយចូល heap ទទេ៖

push 5:   [5]
push 3:   [5, 3]           3 < parent 5, swap          -> [3, 5]
push 8:   [3, 5, 8]        8 >= parent 3, stay
push 1:   [3, 5, 8, 1]     1 < parent 5, swap          -> [3, 1, 8, 5]
                           1 < parent 3, swap          -> [1, 3, 8, 5]
push 9:   [1, 3, 8, 5, 9]  9 >= parent 3, stay
push 2:   [1, 3, 8, 5, 9, 2]  2 < parent 8, swap       -> [1, 3, 2, 5, 9, 8]
                           2 >= parent 1, stop

Array ចុងក្រោយ [1, 3, 2, 5, 9, 8] គឺជា heap ពីរូបក្នុងផ្នែកទី 4 យ៉ាងពិតប្រាកដ។

នេះគឺជាជំហាន sift up ក្នុង code៖

function siftUp(items: number[], index: number): void {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (items[index] >= items[parent]) break; // heap rule holds: stop
    [items[index], items[parent]] = [items[parent], items[index]];
    index = parent;
  }
}

ធាតុអាចឡើងយ៉ាងច្រើនពីបាតទៅ root ដែលជាកម្ពស់របស់ tree ប្រហែល log₂ n level។ នោះជាមូលហេតុដែល push គឺ O(log n)។

7. Pop និង Sift Down

pop ដក root ចេញ ដែលទុកចន្លោះមួយនៅកំពូល។ ល្បិចគឺជៀសវាងការរុញ array ទាំងមូល៖

1. រក្សាទុក root (ចម្លើយ)។
2. យកធាតុ ចុងក្រោយ ក្នុង array ហើយផ្លាស់ទីវាទៅ root។ នេះរក្សារូបរាងឲ្យ complete។
3. ធាតុនោះប្រហែលជាធំពេកសម្រាប់កំពូល។ Sift down៖ ប្រៀបធៀបវាជាមួយ child ទាំងពីររបស់វា ប្តូរវាជាមួយ child ដែល តូចជាង ហើយធ្វើម្តងទៀតរហូតដល់វាមិនធំជាង child ទាំងពីរ ឬវាគ្មាន child។

Pop ពី [1, 3, 2, 5, 9, 8]៖

answer = 1
move last item (8) to the root:  [8, 3, 2, 5, 9]
children of 8 are 3 and 2. Smaller is 2, swap:  [2, 3, 8, 5, 9]
8 is now at index 2. Children at 5 and 6 do not exist. Stop.

ឥឡូវ heap គឺ [2, 3, 8, 5, 9]។ Pop បន្ទាប់នឹង return 2 ហើយបន្តបែបនេះ ផ្តល់ 1, 2, 3, 5, 8, 9 តាមលំដាប់។

ហេតុអ្វីប្តូរជាមួយ child ដែល តូចជាង? ព្រោះ child នោះក្លាយជា parent ថ្មីរបស់ child មួយទៀត ដូច្នេះវាត្រូវតែមិនធំជាង child នោះ។ ប្រសិនបើយើងប្តូរជាមួយ child ដែលធំជាង នោះ child តូចជាងនឹងនៅក្រោមវា ហើយបំបែកច្បាប់ heap។

function siftDown(items: number[], index: number): void {
  const n = items.length;
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

    if (left < n && items[left] < items[smallest]) smallest = left;
    if (right < n && items[right] < items[smallest]) smallest = right;

    if (smallest === index) break; // heap rule holds: stop
    [items[index], items[smallest]] = [items[smallest], items[index]];
    index = smallest;
  }
}

ម្តងទៀត យ៉ាងច្រើនមួយដំណើរពីកំពូលទៅបាត ដូច្នេះ pop គឺ O(log n)។ ការពិនិត្យ left < n និង right < n មានសារៈសំខាន់៖ វាបញ្ឈប់យើងពីការអានហួសចុងនៃ array។

8. ការសាងសង់ PriorityQueue

ឥឡូវនេះយើងរុំវាក្នុង class។ យើងទទួល function compare ជាជម្រើស ដើម្បីឲ្យ code ដូចគ្នាអាចដោះស្រាយលេខ string និង object ហើយដើម្បីឲ្យអ្នកអាចបញ្ច្រាសលំដាប់សម្រាប់ max-heap។ អនុសញ្ញាប្រៀបធៀបគឺដូចគ្នានឹង Array.sort៖ លេខអវិជ្ជមានមានន័យថា "a ទៅមុន"។

type Compare<T> = (a: T, b: T) => number;

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

class PriorityQueue<T> {
  private items: T[] = [];

  constructor(private compare: Compare<T> = defaultCompare) {}

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

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  peek(): T | undefined {
    return this.items[0];
  }

  push(item: T): void {
    this.items.push(item);
    this.siftUp(this.items.length - 1);
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop() as T;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  // siftUp, siftDown and swap go here (see the recipe)
}

កត់សម្គាល់លំដាប់នៅក្នុង pop។ យើងដកធាតុចុងក្រោយចេញមុនដោយ this.items.pop()។ ប្រសិនបើ heap មានធាតុតែមួយ ធាតុចុងក្រោយ គឺ កំពូល ហើយ array ឥឡូវទទេ ដូច្នេះយើងមិនត្រូវដាក់វាត្រឡប់ទៅវិញទេ។ នោះជាមូលហេតុដែលការពិនិត្យ if (this.items.length > 0) មាន។ ការភ្លេចវាគឺជា bug បុរាណដែលទុកធាតុខ្មោចនៅពីក្រោយ។

ការប្រើប្រាស់វា៖

const pq = new PriorityQueue<number>();
for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);

console.log(pq.peek()); // 1
console.log(pq.size);   // 6

const out: number[] = [];
while (!pq.isEmpty()) out.push(pq.pop() as number);
console.log(out.join(" ")); // 1 2 3 5 8 9

ការ pop អ្វីៗទាំងអស់ផ្តល់លទ្ធផលតាមលំដាប់។ តើអ្នកកត់សម្គាល់អ្វីដែលយើងទើបតែធ្វើទេ? នោះគឺជាក្បួនដោះស្រាយ sort។

សម្រាប់ object ត្រូវបញ្ជូន comparator ដែលប្រាប់ថា field មួយណាសម្រេច៖

interface Job {
  name: string;
  priority: number;
}

const jobs = new PriorityQueue<Job>((a, b) => a.priority - b.priority);
jobs.push({ name: "send newsletter", priority: 3 });
jobs.push({ name: "charge card", priority: 1 });
jobs.push({ name: "resize image", priority: 2 });

console.log(jobs.pop()?.name); // charge card

ហើយសម្រាប់ max-heap ត្រូវប្តូរ argument ដើម្បីឲ្យលេខធំជាងរៀបចំមុន៖

const biggestFirst = new PriorityQueue<number>((a, b) => b - a);
for (const n of [5, 3, 8]) biggestFirst.push(n);

console.log(biggestFirst.pop()); // 8

9. Heap Sort និង Top-K

Heap sort។ Push គ្រប់ value ចូល heap បន្ទាប់មក pop ពួកវាទាំងអស់។ រាល់ push និង pop មានតម្លៃ O(log n) ហើយយើងធ្វើយ៉ាងនេះ n ដង ដូច្នេះ sort ទាំងមូលគឺ O(n log n) ដូចគ្នានឹង merge sort ពីជំពូក Sorting៖

function heapSort<T>(
  values: T[],
  compare: Compare<T> = defaultCompare,
): T[] {
  const heap = new PriorityQueue(compare);
  for (const v of values) heap.push(v);

  const sorted: T[] = [];
  while (!heap.isEmpty()) sorted.push(heap.pop() as T);
  return sorted;
}

console.log(heapSort([5, 3, 8, 1, 9, 2]));
// [ 1, 2, 3, 5, 8, 9 ]
console.log(heapSort(["pear", "apple", "fig"]));
// [ 'apple', 'fig', 'pear' ]

កំណែនេះប្រើអង្គចងចាំបន្ថែម O(n) សម្រាប់ heap។ កំណែក្នុងសៀវភៅសិក្សា sort នៅនឹងកន្លែង (in place) ដោយបំប្លែង array input ខ្លួនវាទៅជា heap បន្ទាប់មកប្តូរកំពូលជាមួយធាតុចុងក្រោយដែលមិនទាន់បានរៀបចំម្តងហើយម្តងទៀត។ វាមិនត្រូវការ array បន្ថែមទេ ប៉ុន្តែវាមិន stable ហើយក្នុងការអនុវត្តជាក់ស្តែង quicksort និង merge sort ជាធម្មតាលឿនជាង ព្រោះពួកវាមិត្តភាពនឹង CPU cache ជាង។ តម្លៃពិតរបស់ heap sort គឺករណីអាក្រក់បំផុត O(n log n) ដែលធានា និងគំនិតដែលនៅពីក្រោយវា ដែលជំរុញល្បិចបន្ទាប់។

Top-K។ សំណួរទូទៅខ្លាំង៖ "ពី stream នៃពិន្ទុមួយលាន ផ្តល់ 10 ខ្ពស់បំផុតឲ្យខ្ញុំ"។ វិធីច្បាស់លាស់គឺ sort អ្វីៗទាំងអស់ ហើយយក 10 ដំបូង។ នោះមានតម្លៃ O(n log n) ហើយវាក៏ត្រូវការទិន្នន័យទាំងអស់ក្នុងអង្គចងចាំដែរ។

Heap ធ្វើបានល្អជាង។ រក្សា min-heap ទំហំ K។ សម្រាប់រាល់ value ថ្មី push វា ហើយប្រសិនបើ heap ឥឡូវមានធាតុច្រើនជាង K នោះ pop ធាតុតូចបំផុត។ អ្វីដែលនៅសល់ក្នុង heap នៅចុងបញ្ចប់គឺជា value K ដែលធំបំផុត។ (វាមានអារម្មណ៍ថាបញ្ច្រាសក្នុងការប្រើ min-heap ដើម្បីរកធំបំផុត ប៉ុន្តែធាតុតូចបំផុតក្នុង K ដែលល្អបំផុតបច្ចុប្បន្នគឺជាធាតុដែលត្រូវបណ្តេញចេញមុនគេ ហើយនោះគឺជាអ្វីដែល min-heap ប្រគល់ឲ្យអ្នកយ៉ាងពិតប្រាកដ។)

function topK(values: number[], k: number): number[] {
  const heap = new PriorityQueue<number>();
  for (const v of values) {
    heap.push(v);
    if (heap.size > k) heap.pop(); // drop the smallest of the k + 1
  }

  const result: number[] = [];
  while (!heap.isEmpty()) result.push(heap.pop() as number);
  return result.reverse(); // biggest first
}

console.log(topK([4, 9, 1, 7, 3, 8, 2], 3));
// [ 9, 8, 7 ]

Heap មិនដែលផ្ទុកធាតុលើសពី K + 1 ទេ ដូច្នេះប្រតិបត្តិការនីមួយៗមានតម្លៃ O(log K) ហើយការងារទាំងមូលគឺពេលវេលា O(n log K) និងអង្គចងចាំ O(K)។ នៅពេល K គឺ 10 និង n គឺមួយលាន log K គឺប្រហែល 3 ធៀបនឹងប្រហែល 20 សម្រាប់ sort ពេញលេញ ហើយអ្នកមិនដែលត្រូវការរក្សា value មួយលាននៅក្នុងពេលតែមួយទេ។ នេះគឺជារបៀបដែលបញ្ជី "trending now", leaderboard និងឧបករណ៍ "ឯកសារ 10 ធំបំផុតក្នុង folder នេះ" ដំណើរការ។

សូមកត់សម្គាល់ការពិតមួយទៀតអំពី heap៖ ការសាងសង់ heap ពី value n ដែលអ្នកមានរួចហើយ អាចធ្វើបានក្នុង O(n) (មិនមែន O(n log n)) ដោយវិធីសាស្ត្រពីក្រោមឡើងលើដ៏ឆ្លាតហៅថា "heapify" ដែល sift down ចាប់ផ្តើមពីកណ្តាលនៃ array។ Loop push ម្តងមួយដែលយើងប្រើក្នុងជំពូកនេះគឺ O(n log n) ដែលល្អគ្រប់គ្រាន់សម្រាប់ស្ទើរតែគ្រប់រឿង។

10. បញ្ហាពិត៖ Scheduler, Median, Merge

Task scheduler។ ការងារផ្ទៃខាងក្រោយមកដល់ជាមួយអាទិភាព។ Worker យកការងារបន្ទាន់បំផុតម្តងហើយម្តងទៀត។ មានព័ត៌មានលម្អិតមួយត្រូវដោះស្រាយ៖ ការងារដែលមានអាទិភាព ដូចគ្នា គួររត់តាមលំដាប់ដែលពួកវាមកដល់។ Heap មិនសន្យារឿងនេះដោយខ្លួនវាទេ (វាមិន stable) ដូច្នេះយើងបន្ថែម counter នៃការមកដល់ជា tiebreaker៖

interface Task {
  name: string;
  priority: number;
  order: number;
}

const tasks = new PriorityQueue<Task>(
  (a, b) => a.priority - b.priority || a.order - b.order,
);

let counter = 0;
const add = (name: string, priority: number) =>
  tasks.push({ name, priority, order: counter++ });

add("send newsletter", 3);
add("charge card", 1);
add("resize image", 2);
add("send receipt", 1);
add("clean logs", 5);

const runOrder: string[] = [];
while (!tasks.isEmpty()) runOrder.push((tasks.pop() as Task).name);

console.log(runOrder);
// [ 'charge card', 'send receipt', 'resize image', 'send newsletter', 'clean logs' ]

កន្សោម a.priority - b.priority || a.order - b.order មានន័យថា "ប្រៀបធៀបតាមអាទិភាព ហើយប្រសិនបើនោះផ្តល់ 0 ប្រៀបធៀបតាមលំដាប់នៃការមកដល់"។ ការងារអាទិភាព 1 ទាំងពីរមកមុន ហើយ charge card យកឈ្នះ send receipt ព្រោះវាត្រូវបានបន្ថែមមុន។

Job queue ពិតប្រាកដ (Sidekiq, BullMQ, សេវាកម្ម cloud task) ត្រូវបានសាងសង់លើគំនិតដូចគ្នា ដោយទិន្នន័យត្រូវបានរក្សាទុកក្នុង Redis ឬ database ជំនួសឲ្យអង្គចងចាំ។

Kth largest ក្នុង stream។ លេខបន្តមកដល់ ហើយបន្ទាប់ពីលេខនីមួយៗ អ្នកត្រូវរាយការណ៍លេខធំបំផុតទី k រហូតមកដល់ពេលនេះ។ វាគឺជាល្បិច top-K ម្តងទៀត៖ heap ទំហំ k មានចម្លើយនៅកំពូល ព្រោះធាតុតូចបំផុតក្នុង k ធំបំផុតគឺជាធាតុធំបំផុតទី k៖

class KthLargest {
  private heap = new PriorityQueue<number>();

  constructor(private k: number, nums: number[]) {
    for (const n of nums) this.add(n);
  }

  add(value: number): number {
    this.heap.push(value);
    if (this.heap.size > this.k) this.heap.pop();
    return this.heap.peek() as number;
  }
}

const third = new KthLargest(3, [4, 5, 8, 2]);
console.log(third.add(3));  // 4
console.log(third.add(5));  // 5
console.log(third.add(10)); // 5
console.log(third.add(9));  // 8
console.log(third.add(4));  // 8

តាមដានបន្ទាត់ទីមួយ។ បន្ទាប់ពី constructor ធំបំផុតទាំងបីនៃ 4, 5, 8, 2 គឺ 4, 5, 8 ដូច្នេះ heap ផ្ទុកពួកវា។ ការបន្ថែម 3 ធ្វើឲ្យមានធាតុបួន ហើយធាតុតូចបំផុត (3) ត្រូវបាន pop ដូច្នេះចម្លើយនៅតែជា 4។

បញ្ចូលបញ្ជីដែលបានរៀបចំ K (Merge K sorted lists)។ អ្នកមានបញ្ជីជាច្រើនដែលបានរៀបចំរួចហើយ ឧទាហរណ៍ឯកសារ log បីដែលបានរៀបចំពី server បី ហើយចង់បានបញ្ជីរួមបញ្ចូលគ្នាមួយដែលបានរៀបចំ។ ការពិនិត្យខាងមុខនៃរាល់បញ្ជីរាល់ពេលដំណើរការបាន ប៉ុន្តែមានតម្លៃ O(k) ក្នុងមួយធាតុ។ Heap នៃធាតុខាងមុខបច្ចុប្បន្នរបស់បញ្ជីនីមួយៗផ្តល់ធាតុតូចបំផុតក្នុង O(log k)៖

function mergeSorted(lists: number[][]): number[] {
  const heap = new PriorityQueue<{ value: number; list: number; index: number }>(
    (a, b) => a.value - b.value,
  );

  lists.forEach((l, i) => {
    if (l.length > 0) heap.push({ value: l[0], list: i, index: 0 });
  });

  const out: number[] = [];
  while (!heap.isEmpty()) {
    const { value, list, index } = heap.pop()!;
    out.push(value);
    const next = index + 1;
    if (next < lists[list].length) {
      heap.push({ value: lists[list][next], list, index: next });
    }
  }
  return out;
}

console.log(mergeSorted([[1, 4, 7], [2, 5], [3, 6, 9]]));
// [ 1, 2, 3, 4, 5, 6, 7, 9 ]

ធាតុដែលត្រូវបាន pop នីមួយៗចងចាំថាវាមកពីបញ្ជីណា ដូច្នេះយើងដឹងថាត្រូវយកធាតុបន្ទាប់ពីបញ្ជីណា។ តម្លៃសរុបគឺ O(n log k) សម្រាប់ធាតុ n ក្នុងបញ្ជី k។ នេះគឺជាជំហាន "merge" នៃ external sorting ដែលប្រើនៅពេលទិន្នន័យធំពេកមិនអាចដាក់ក្នុងអង្គចងចាំបាន។

Median ដែលកំពុងដំណើរការ (Running median)។ បន្ទាប់ពីលេខថ្មីនីមួយៗ រាយការណ៍ median (value កណ្តាល) នៃអ្វីៗទាំងអស់ដែលបានឃើញរហូតមកដល់ពេលនេះ។ ការ sort រាល់ពេលគឺយឺតពេក។ ចម្លើយដ៏ឆើតឆាយប្រើ heap ពីរ៖ max-heap សម្រាប់ពាក់កណ្តាលតូចជាងនៃលេខ និង min-heap សម្រាប់ពាក់កណ្តាលធំជាង។ បន្ទាប់មក median នៅលើកំពូលនៃ heap មួយ ឬជាមធ្យមនៃកំពូលទាំងពីរ៖

class RunningMedian {
  private low = new PriorityQueue<number>((a, b) => b - a); // max-heap
  private high = new PriorityQueue<number>();               // min-heap

  add(value: number): void {
    if (this.low.isEmpty() || value <= (this.low.peek() as number)) {
      this.low.push(value);
    } else {
      this.high.push(value);
    }
    // Keep the sizes equal, or `low` one bigger.
    if (this.low.size > this.high.size + 1) {
      this.high.push(this.low.pop() as number);
    } else if (this.high.size > this.low.size) {
      this.low.push(this.high.pop() as number);
    }
  }

  median(): number {
    if (this.low.size > this.high.size) return this.low.peek() as number;
    return ((this.low.peek() as number) + (this.high.peek() as number)) / 2;
  }
}

const rm = new RunningMedian();
const medians: number[] = [];
for (const n of [5, 2, 8, 1, 9, 3]) {
  rm.add(n);
  medians.push(rm.median());
}
console.log(medians);
// [ 5, 3.5, 5, 3.5, 5, 4 ]

ពិនិត្យ value ចុងក្រោយ៖ លេខគឺ 1, 2, 3, 5, 8, 9។ ពីរកណ្តាលគឺ 3 និង 5 ហើយជាមធ្យមគឺ 4។ រាល់ add គឺ O(log n) ហើយ median គឺ O(1)។

11. រូបមន្ត៖ priority-queue.ts សម្រាប់ algolab

បង្កើត src/priority-queue.ts ក្នុង algolab៖

export type Compare<T> = (a: T, b: T) => number;

// A binary heap stored in a plain array. The item that sorts FIRST
// according to `compare` (the smallest) is always at index 0.
export class PriorityQueue<T> {
  private items: T[] = [];

  constructor(private compare: Compare<T> = defaultCompare) {}

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

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  peek(): T | undefined {
    return this.items[0];
  }

  push(item: T): void {
    this.items.push(item);
    this.siftUp(this.items.length - 1);
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop() as T;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  private siftUp(index: number): void {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.compare(this.items[index], this.items[parent]) >= 0) break;
      this.swap(index, parent);
      index = parent;
    }
  }

  private siftDown(index: number): void {
    const n = this.items.length;
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;
      if (left < n && this.compare(this.items[left], this.items[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compare(this.items[right], this.items[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }

  private swap(i: number, j: number): void {
    [this.items[i], this.items[j]] = [this.items[j], this.items[i]];
  }
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

export function heapSort<T>(
  values: T[],
  compare: Compare<T> = defaultCompare,
): T[] {
  const heap = new PriorityQueue(compare);
  for (const v of values) heap.push(v);
  const sorted: T[] = [];
  while (!heap.isEmpty()) sorted.push(heap.pop() as T);
  return sorted;
}

// The k largest values, biggest first. Keeps a min-heap of size k.
export function topK(values: number[], k: number): number[] {
  const heap = new PriorityQueue<number>();
  for (const v of values) {
    heap.push(v);
    if (heap.size > k) heap.pop();
  }
  const result: number[] = [];
  while (!heap.isEmpty()) result.push(heap.pop() as number);
  return result.reverse();
}

បង្កើត test ក្នុង src/priority-queue.test.ts៖

import { test } from "node:test";
import assert from "node:assert/strict";
import { PriorityQueue, heapSort, topK } from "./priority-queue.ts";

test("pop returns items smallest first", () => {
  const pq = new PriorityQueue<number>();
  for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);
  assert.equal(pq.peek(), 1);
  const out: number[] = [];
  while (!pq.isEmpty()) out.push(pq.pop() as number);
  assert.deepEqual(out, [1, 2, 3, 5, 8, 9]);
});

test("empty queue returns undefined", () => {
  const pq = new PriorityQueue<number>();
  assert.equal(pq.pop(), undefined);
  assert.equal(pq.peek(), undefined);
  assert.equal(pq.size, 0);
});

test("a comparator turns it into a max-heap", () => {
  const pq = new PriorityQueue<number>((a, b) => b - a);
  for (const n of [5, 3, 8]) pq.push(n);
  assert.equal(pq.pop(), 8);
});

test("works with objects and a priority field", () => {
  const pq = new PriorityQueue<{ name: string; priority: number }>(
    (a, b) => a.priority - b.priority,
  );
  pq.push({ name: "email", priority: 3 });
  pq.push({ name: "payment", priority: 1 });
  pq.push({ name: "report", priority: 2 });
  assert.equal(pq.pop()?.name, "payment");
  assert.equal(pq.pop()?.name, "report");
});

test("heapSort matches Array.sort on random data", () => {
  const data = Array.from({ length: 200 }, () =>
    Math.floor(Math.random() * 1000),
  );
  assert.deepEqual(heapSort(data), [...data].sort((a, b) => a - b));
});

test("topK returns the k largest, biggest first", () => {
  assert.deepEqual(topK([4, 9, 1, 7, 3, 8, 2], 3), [9, 8, 7]);
  assert.deepEqual(topK([1, 2], 5), [2, 1]);
});

test heapSort គឺជាទម្លាប់ល្អ៖ ប្រៀបធៀបក្បួនដោះស្រាយរបស់អ្នកជាមួយ built-in ដែលអាចទុកចិត្តបានលើទិន្នន័យចៃដន្យ ដែលចាប់បានកំហុសក្នុង siftUp និង siftDown ដែលឧទាហរណ៍ជ្រើសរើសដោយដៃអាចខកខាន។ រត់ test៖

npx tsx --test

បន្ថែម export ទៅ src/index.ts៖

export * from "./priority-queue.ts";

បន្ទាប់មកបង្កើត demo-heap.ts នៅក្នុង root របស់ project៖

import { PriorityQueue, heapSort, topK } from "./src/priority-queue.ts";

const pq = new PriorityQueue<number>();
for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);
console.log("peek:", pq.peek(), "size:", pq.size);

const out: number[] = [];
while (!pq.isEmpty()) out.push(pq.pop() as number);
console.log("popped:", out.join(" "));

console.log("heapSort:", heapSort([5, 3, 8, 1, 9, 2]).join(" "));
console.log("top 3:", topK([4, 9, 1, 7, 3, 8, 2], 3).join(" "));

const jobs = new PriorityQueue<{ name: string; priority: number }>(
  (a, b) => a.priority - b.priority,
);
jobs.push({ name: "send newsletter", priority: 3 });
jobs.push({ name: "charge card", priority: 1 });
jobs.push({ name: "resize image", priority: 2 });
console.log("next job:", jobs.pop()?.name);

រត់វា៖

npx tsx demo-heap.ts

peek: 1 size: 6
popped: 1 2 3 5 8 9
heapSort: 1 2 3 5 8 9
top 3: 9 8 7
next job: charge card

អ្នកនឹងប្រើ PriorityQueue ម្តងទៀតក្នុងជំពូកបន្ទាប់ ដែលវាជាម៉ាស៊ីននៃក្បួនដោះស្រាយផ្លូវខ្លីបំផុតរបស់ Dijkstra។

12. សាកល្បងដោយខ្លួនឯង

1. តាមដានដោយដៃ។ Push 7, 4, 9, 2, 6 ចូល min-heap ទទេ ហើយសរសេរ array បន្ទាប់ពីរាល់ការ push។ បន្ទាប់មក pop ម្តង ហើយសរសេរ array ម្តងទៀត។ ពិនិត្យចម្លើយរបស់អ្នកដោយ log heap ក្នុង code (អ្នកប្រហែលត្រូវបង្ហាញ items ជាបណ្តោះអាសន្ន)។
2. Max-heap។ ដោយប្រើតែ class PriorityQueue បង្កើតរចនាសម្ព័ន្ធដែល return string ដែល វែងបំផុត តាមប្រវែងជានិច្ច។ (ព័ត៌មានជំនួយ៖ comparator។)
3. Kth smallest។ សរសេរ kthSmallest(values, k)។ តើអ្នករក្សា heap ប្រភេទណា និងទំហំប៉ុន្មាន? ប្រៀបធៀបជាមួយ topK។
4. ជិតសូន្យបំផុត។ ផ្តល់ array នៃលេខ return លេខ 3 ដែលជិត 0 បំផុត។ ប្រើ heap ជាមួយ comparator ដែលមើល Math.abs។ តើលំដាប់ដែលអ្នក pop អាស្រ័យលើរបៀបដែលអ្នកសរសេរ comparator ឬទេ?
5. សម្ភាសន៍៖ top K frequent words។ ផ្តល់ array នៃពាក្យ និងលេខ k return ពាក្យ k ដែលញឹកញាប់បំផុត ពាក្យញឹកញាប់បំផុតមកមុន ហើយបើស្មើគ្នាត្រូវរៀបតាមអក្ខរក្រម។ រាប់ដោយ Map (មើល Hash Map និង Set) បន្ទាប់មកប្រើ heap ទំហំ k។ តើភាពស្មុគស្មាញជាអ្វី ហើយវាប្រៀបធៀបនឹងការ sort ពាក្យខុសគ្នាទាំងអស់យ៉ាងដូចម្តេច?
6. សម្ភាសន៍៖ ភ្ជាប់ខ្សែពួរ។ អ្នកមានខ្សែពួរដែលមានប្រវែងផ្សេងៗគ្នា។ ការភ្ជាប់ខ្សែពួរពីរមានតម្លៃស្មើនឹងផលបូកនៃប្រវែងរបស់ពួកវា។ រកតម្លៃសរុបថោកបំផុតដើម្បីភ្ជាប់ពួកវាទាំងអស់ទៅជាមួយ។ សម្រាប់ [4, 3, 2, 6] ចម្លើយគឺ 29។ ព័ត៌មានជំនួយ៖ តែងតែភ្ជាប់ពីរខ្លីបំផុត។ តើនោះប្រាប់អ្នកឲ្យប្រើអ្វី?
7. ធ្វើបច្ចុប្បន្នភាពអាទិភាព។ Heap របស់យើងគ្មានវិធីប្តូរអាទិភាពរបស់ធាតុបន្ទាប់ពីវាត្រូវបាន push ទេ។ តើអ្នកអាចធ្វើវាដោយអ្វីដែលយើងមានយ៉ាងដូចម្តេច? (ល្បិចទូទៅមួយ៖ push ច្បាប់ចម្លងថ្មី ហើយរំលងច្បាប់ចម្លងដែលហួសសម័យនៅពេលពួកវាចេញមក។ អ្នកនឹងឃើញល្បិចនេះយ៉ាងពិតប្រាកដក្នុងក្បួនដោះស្រាយរបស់ Dijkstra ក្នុងជំពូកបន្ទាប់។)

Priority queue គឺជាជួរដែលធាតុសំខាន់បំផុតនៅខាងមុខជានិច្ច ហើយ heap ធ្វើឲ្យវាថោក។ ជាមួយ tree និង heap នៅក្នុងដៃ អ្នកត្រៀមខ្លួនរួចជាស្រេចសម្រាប់រចនាសម្ព័ន្ធទូទៅបំផុត៖ ធាតុដែលតភ្ជាប់គ្នាតាមរបៀបណាក៏បាន។ ក្នុង Graph យើងបង្កើតគំរូផែនទី បណ្តាញ និង dependency ស្វែងរកតាមវាដោយ BFS និង DFS ហើយប្រើ PriorityQueue ថ្មីរបស់អ្នកដើម្បីរកផ្លូវថោកបំផុត។