Очередь с приоритетом на JavaScript через бинарную кучу

Очередь с приоритетом на JavaScript можно реализовать через бинарную кучу. Она нужна для приоритизации задач в клиентах и планировщиках. Максимальная куча хранит в корне элемент с наибольшим приоритетом.

Вы научитесь реализовывать бинарную кучу и операции insert и extractMax. Пример с задачами покажет создание очереди, просмотр и извлечение элементов.

Куча

Бинарная куча – это древовидная структура данных для реализации приоритетной очереди. Массив хранит ее узлы по уровням, слева направо. Различают два варианта упорядочения кучи:

  1. Минимальная – значение родителя не больше значений его дочерних узлов.
  2. Максимальная – значение родителя не меньше значений его дочерних узлов.

Слово «двоичная» описывает форму дерева: узел имеет максимум 2 дочерних узла. В статье реализована максимальная двоичная куча для числовых приоритетов.

Представление максимальной кучи в виде массива и двоичного дерева

На изображении показана максимальная куча с элементами 26, 24, 20, 18 и 17. Корень содержит число 26, а его дочерние узлы – 24 и 20.

Куча не требует полной сортировки массива.

Она задает порядок только между родителями и дочерними узлами. Например, массив [26, 18, 24, 17, 10] тоже представляет максимальную кучу.

Новый элемент сначала занимает свободное место в конце массива. В дереве это следующая позиция на нижнем уровне слева направо.

Если приоритет нарушает порядок кучи, элемент поднимается к корню.

Терминология

  • Узел хранит один элемент дерева.
  • Ветвь, или ребро, соединяет родителя с дочерним узлом.
  • Корень занимает верхний уровень дерева. В максимальной куче он содержит наибольшее значение.
  • Дочерние узлы непосредственно связаны с родителем. В двоичной куче их не больше 2: левый и правый. Их значения не превышают значение родителя в максимальной куче.
  • Родитель расположен на один уровень выше своего дочернего узла.
  • Высота дерева равна числу ребер на самом длинном пути от корня до листа.

Методы очереди с приоритетом

Очередь предоставляет 3 основные операции. Еще 2 метода помогают поддерживать порядок элементов:

  • peek() возвращает корень без удаления.
  • insert(element) добавляет числовой приоритет.
  • extractMax() удаляет и возвращает максимальный элемент.
  • swap(indexOne, indexTwo) меняет местами элементы массива.
  • heapify(index) восстанавливает порядок поддерева, опуская элемент вниз.

Для минимальной кучи операция extractMin() удаляет и возвращает минимум. Ее реализация приведена вместе с изменениями сравнений.

Вспомогательные функции

В массиве индексы родителя и дочерних узлов вычисляются по формулам. Добавьте эти функции перед конструктором кучи:

const leftChild = (index) => index * 2 + 1;
const rightChild = (index) => index * 2 + 2;
const parent = (index) => Math.floor((index - 1) / 2);

Индекс левого дочернего узла равен 2 * index + 1. Индекс правого равен 2 * index + 2.

Чтобы получить индекс родителя, вычтите 1 и разделите результат на 2. Функция Math.floor() округляет результат вниз.

Для корня с индексом 0 родителя нет, поэтому цикл в insert останавливается на индексе 0.

Индексы родителя и потомков узла бинарной кучи

Конструктор

Инициализируем кучу как пустой массив:

function MaxHeap() {
  this.heap = [];
}

Создавайте экземпляры через new MaxHeap().

Имя конструктора чувствительно к регистру: все методы используют MaxHeap.prototype.

Swap

Метод swap меняет местами два элемента в массиве. Он используется во время вставки и извлечения.

MaxHeap.prototype.swap = function (indexOne, indexTwo) {
  const tmp = this.heap[indexOne];
  this.heap[indexOne] = this.heap[indexTwo];
  this.heap[indexTwo] = tmp;
};

Peek

Метод peek показывает текущий корень кучи. Он не извлекает корневой узел из дерева.

MaxHeap.prototype.peek = function () {
  return this.heap[0];
};

В пустой куче обращение к индексу 0 возвращает undefined.

Insert

Метод insert добавляет элемент в конец массива. Затем цикл сравнивает новый элемент с его родителем. Если элемент больше, метод меняет их местами и продолжает подъем.

MaxHeap.prototype.insert = function (element) {
  this.heap.push(element);
  let index = this.heap.length - 1;

  while (index !== 0 && this.heap[index] > this.heap[parent(index)]) {
    this.swap(index, parent(index));
    index = parent(index);
  }
};

Цикл останавливается у корня или при восстановлении порядка с родителем.

Равные значения допустимы и не требуют перестановки.

ExtractMax

Метод extractMax извлекает корень и восстанавливает порядок кучи. Вместо сдвига массива метод переносит последний элемент на позицию 0. Затем heapify(0) опускает этот элемент на подходящее место.

MaxHeap.prototype.extractMax = function () {
  if (this.heap.length === 0) {
    return undefined;
  }

  if (this.heap.length === 1) {
    return this.heap.pop();
  }

  const root = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.heapify(0);

  return root;
};

Пустая очередь возвращает undefined и остается пустой. Очередь из одного элемента возвращает его через pop(). Метод не добавляет дубликаты и не оставляет пустые элементы.

Heapify

Метод heapify сравнивает текущий узел с обоими дочерними узлами. Переменная largest хранит индекс наибольшего из этих элементов. Если максимум находится ниже, метод меняет его местами с текущим узлом.

MaxHeap.prototype.heapify = function (index) {
  const left = leftChild(index);
  const right = rightChild(index);
  let largest = index;

  if (left < this.heap.length && this.heap[largest] < this.heap[left]) {
    largest = left;
  }

  if (right < this.heap.length && this.heap[largest] < this.heap[right]) {
    largest = right;
  }

  if (largest !== index) {
    this.swap(largest, index);
    this.heapify(largest);
  }
};

Рекурсивный вызов продолжает проверку с позиции опущенного элемента. Метод останавливается, когда родитель не меньше дочерних узлов.

Вызов предполагает, что оба дочерних поддерева уже соблюдают порядок кучи. Именно такое состояние возникает после переноса последнего элемента в корень.

Случаи применения

Очередь с приоритетом помогает планировщику выбирать следующую задачу. В максимальной куче большее число означает более высокий приоритет.

Соберите функции, конструктор и методы в один файл heap.js. Добавьте пример после всех определений и запустите файл в среде JavaScript. Также можно выполнить весь код по порядку в консоли браузера.

Пример хранит в куче числа, а названия задач – отдельно. Здесь каждая задача имеет уникальный приоритет.

const tasks = new Map([
  [3, "Обновить документацию"],
  [10, "Исправить ошибку оплаты"],
  [5, "Добавить фильтр задач"]
]);

const queue = new MaxHeap();
queue.insert(3);
queue.insert(10);
queue.insert(5);

console.log(queue.peek());
console.log(tasks.get(queue.extractMax()));
console.log(tasks.get(queue.extractMax()));
console.log(tasks.get(queue.extractMax()));
console.log(queue.extractMax());
console.log(queue.heap.length);

Ожидаемый вывод показывает порядок задач и состояние пустой очереди:

10
Исправить ошибку оплаты
Добавить фильтр задач
Обновить документацию
undefined
0

Вызов peek() оставляет число 10 в очереди.

Последовательные вызовы extractMax() возвращают приоритеты 10, 5 и 3. Последнее извлечение проверяет пустую очередь, а длина массива остается равной 0.

Числовая реализация не сравнивает объекты задач по полю priority. Для нескольких задач с одинаковым приоритетом потребуется другое хранение задач. Например, каждому приоритету можно сопоставить массив задач вместо одного названия.

Сложность операций с кучей

Пусть n обозначает число элементов в куче. В стандартной модели массива операции имеют следующую сложность:

  • insert – O(log n).
  • peek – O(1).
  • extractMax и extractMin – O(log n).

При вставке новый элемент поднимается вверх, самое большее до корня. Число сравнений не превышает высоту дерева. Высота полной двоичной кучи растет как log n.

При извлечении heapify проходит один путь от корня вниз. На каждом уровне метод выполняет не больше 2 сравнений значений.

Перенос последнего элемента в корень не требует сдвига остальных элементов.

Оценки описывают работу алгоритма с массивом и число сравнений. Расширение внутреннего хранилища массива зависит от движка JavaScript.

Как перейти от максимальной кучи к минимальной

В минимальной куче наименьший элемент должен находиться в корне. Для отдельной реализации скопируйте конструктор и методы, заменив MaxHeap на MinHeap. Функции индексов, методы swap и peek оставьте без изменений.

Измените сравнения в двух методах:

  • В insert замените условие подъема на index !== 0 && this.heap[index] < this.heap[parent(index)].
  • В heapify переименуйте largest в smallest во всех строках.
  • В проверке левого узла используйте this.heap[smallest] > this.heap[left], а правого – this.heap[smallest] > this.heap[right]. Проверки границ массива сохраните.

Вместо extractMax добавьте метод extractMin. Сам перенос последнего элемента не зависит от направления сравнений:

MinHeap.prototype.extractMin = function () {
  if (this.heap.length === 0) {
    return undefined;
  }

  if (this.heap.length === 1) {
    return this.heap.pop();
  }

  const root = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.heapify(0);

  return root;
};

После этих изменений очередь извлекает числа в порядке возрастания. Для вставок 3, 10 и 5 последовательные извлечения вернут 3, 5 и 10.

Крайние случаи полезно покрыть отдельными вызовами: пустая куча, один элемент и повторяющиеся приоритеты. Для пустой и одноэлементной кучи extractMax() уже работает отдельно, а повторы требуют хранить массив задач на приоритет.

Комментарии

Оставьте свой комментарий
Пока никто не оставил комментариев