Будова ефективної черги з пріоритетами в JavaScript з приватними методами - javascript.org.ua

Управління завданнями за пріоритетом є фундаментальним концептом в інформатиці, часто реалізованим за допомогою черги з пріоритетом (Priority Queue). Черга з пріоритетом надає пріоритети елементам, гарантуючи, що елемент з найвищим пріоритетом (або найменшим ключем) буде оброблений першим.

У цьому пості блогу ми пройдемо через побудову ефективної черги з пріоритетом у JavaScript, використовуючи структуру мін-кучі (min-heap).
Ми також інкапсулюємо внутрішні методи за допомогою приватних полів класу (private class fields), забезпечуючи, щоб був відкритий лише необхідний API.

Чому використовувати чергу з пріоритетом?

Черги з пріоритетом використовуються в численних ситуаціях, таких як:

Планування завдань (Task Scheduling): Призначення завдань на основі рівнів пріоритету.
Алгоритм Дейкстри (Dijkstra’s Algorithm): Рішення задачі знаходження найкоротшого шляху.
Моделювання подій (Event Simulation): Обробка подій у порядку їх міток часу.

Наївна реалізація за допомогою масивів вимагала б O(n) для вставки або видалення, але структура бінарної купи (binary heap) зменшує це до O(log⁡n), що робить її ідеальною для масштабованих застосунків.

План

Ми реалізуємо чергу з пріоритетом на основі мін-купи (Min-Heap):

Мін-купа (Min-Heap): Гарантує, що найменший ключ завжди буде на корені.
Інкапсуляція (Encapsulation): Використовуємо приватні поля та методи, щоб приховати внутрішні операції.
Публічний API (Public API):
- enqueue(key, value): Вставити пару ключ-значення в чергу.
- dequeue(): Видалити та повернути пару з найменшим ключем.
- peek(): Переглянути пару з найменшим ключем без її видалення.
- isEmpty(): Перевірити, чи пуста черга.
- size(): Отримати кількість елементів у черзі.

Реалізація

Ось реалізація черги з пріоритетом:

class PriorityQueue {  
 #heap; // Приватне поле для збереження масиву купи  

 constructor() {  
 this.#heap = []; // Ініціалізація приватної купи  
 }  

 // Публічний метод: Вставка пари ключ-значення в купу  
 enqueue(key, value) {  
 const newItem = { key, value };  
 this.#heap.push(newItem);  
 this.#bubbleUp(this.#heap.length - 1);  
 }  

 // Публічний метод: Видалення елемента з найвищим пріоритетом (найменший ключ)  
 dequeue() {  
 if (this.isEmpty()) {  
 throw new Error("Черга з пріоритетом пуста.");  
 }  
 if (this.#heap.length === 1) {  
 return this.#heap.pop();  
 }  

 const top = this.#heap[0]; // Корінь (найменший ключ)  
 this.#heap[0] = this.#heap.pop();  
 this.#bubbleDown(0);  
 return top;  
 }  

 // Публічний метод: Переглянути елемент з найвищим пріоритетом без його видалення  
 peek() {  
 if (this.isEmpty()) {  
 throw new Error("Черга з пріоритетом пуста.");  
 }  
 return this.#heap[0];  
 }  

 // Публічний метод: Перевірити, чи пуста черга з пріоритетом  
 isEmpty() {  
 return this.#heap.length === 0;  
 }  

 // Публічний метод: Отримати розмір черги з пріоритетом  
 size() {  
 return this.#heap.length;  
 }  

 // Приватний метод: Висувати елемент на заданому індексі  
 #bubbleUp(index) {  
 while (  
 index > 0 &&  
 this.#heap[index].key < this.#heap[this.#getParentIndex(index)].key  
 ) {  
 const parentIndex = this.#getParentIndex(index);  
 this.#swap(index, parentIndex);  
 index = parentIndex;  
 }  
 }  

 // Приватний метод: Опускати елемент на заданому індексі  
 #bubbleDown(index) {  
 const size = this.#heap.length;  

 while (true) {  
 const leftIndex = this.#getLeftChildIndex(index);  
 const rightIndex = this.#getRightChildIndex(index);  
 let smallestIndex = index;  

 if (  
 leftIndex < size &&  
 this.#heap[leftIndex].key < this.#heap[smallestIndex].key  
 ) {  
 smallestIndex = leftIndex;  
 }  

 if (  
 rightIndex < size &&  
 this.#heap[rightIndex].key < this.#heap[smallestIndex].key  
 ) {  
 smallestIndex = rightIndex;  
 }  

 if (smallestIndex === index) {  
 break;  
 }  

 this.#swap(index, smallestIndex);  
 index = smallestIndex;  
 }  
 }  

 // Приватні допоміжні методи  
 #getParentIndex(index) {  
 return Math.floor((index - 1) / 2);  
 }  

 #getLeftChildIndex(index) {  
 return 2 * index + 1;  
 }  

 #getRightChildIndex(index) {  
 return 2 * index + 2;  
 }  

 #swap(index1, index2) {  
 [this.#heap[index1], this.#heap[index2]] = [this.#heap[index2], this.#heap[index1]];  
 }  
}

Основні особливості реалізації

Ефективні операції (Efficient Operations):

Вставка та видалення (Insertion and Deletion): O(log⁡n), завдяки збалансованій бінарній деревоподібній структурі купи.
Перегляд (Peek): O(1), оскільки найменший елемент завжди знаходиться на корені.

Інкапсуляція (Encapsulation):
- Приватні методи та поля (префікс #) приховують внутрішню купу та допоміжні функції.
- Тільки публічні методи (enqueue, dequeue, peek тощо) доступні для використання.

Мін-купа (Min-Heap): Найменший ключ завжди знаходиться на корені купи, що забезпечує ефективне управління пріоритетами.

Приклад використання

const pq = new PriorityQueue();  

// Вставка пар ключ-значення  
pq.enqueue(3, "Завдання A");  
pq.enqueue(1, "Завдання B");  
pq.enqueue(2, "Завдання C");  

console.log("Перегляд:", pq.peek()); // { key: 1, value: "Завдання B" }  

// Видалення елементів за пріоритетом  
console.log("Видалити:", pq.dequeue()); // { key: 1, value: "Завдання B" }  
console.log("Видалити:", pq.dequeue()); // { key: 2, value: "Завдання C" }  
console.log("Видалити:", pq.dequeue()); // { key: 3, value: "Завдання A" }  

// Перевірка, чи пуста черга  
console.log("Пуста?", pq.isEmpty()); // true

Висновок

У цьому пості ми реалізували ефективну чергу з пріоритетом за допомогою Мін-купи (Min-Heap) в JavaScript.
Використовуючи приватні поля класів, ми забезпечили належне інкапсуляцію, відкриваючи тільки необхідну функціональність. Ця реалізація є масштабованою і може ефективно обробляти завдання або події за пріоритетом.

Не соромтеся використовувати цю реалізацію у своїх проектах, а також діліться своїми думками або покращеннями в коментарях нижче!

Перекладено з: Building an Efficient Priority Queue in JavaScript with Private Methods