Как с помощью JavaScript создать очередь с приоритетом

Очередь с приоритетом – это абстрактный тип данных, в котором элементы очереди имеют заданный уровень приоритета. Традиционная очередь действует по правилу «первый пришел – первым обслужен. Очередь с приоритетами позволяет более важному элементу перейти вперед и пройти весь путь до начала строки.

Куча

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

1. Минимальная.
2. Максимальная (двоичная).

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

На приведенном выше изображении показан отсортированный массив, который может быть представлен в виде двоичного дерева с элементами: 26, 24, 20, 18 и 17

Каждый элемент добавляется в дерево слева направо. Новый элемент стал бы левым потомком узла, который имеет уровень приоритета 20, предполагая, что элемент имел меньший приоритет, чем этот.

Первый узел, 26, называется корневым узлом. В куче узел с наивысшим приоритетом, который должен быть извлечен следующим. Каждый узел может иметь левого потомка и правого потомка.

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

Элементы с любым значением приоритета могут быть вставлены в кучу. При каждой вставке выполняется упорядочение для правильного позиционирования нового элемента.

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

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

Реализация

Публичные методы:

• swap
• peek
• insert
• extractMax
• heapify

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

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

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

Чтобы получить позицию левого потомка узла, мы умножаем индекс на 2 и добавляем 1 (2n + 1) .

Чтобы получить дочерний элемент узла, умножаем индекс на 2 и добавляем 2 (2n + 2) .

Чтобы получить родителя узла, вычитаем из индекса 1 и делим на 2. Затем округляем все числа с плавающей запятой, которые получаем при делении нечетного числа ((n - 1) / 2).

Конструктор

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

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

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];
	}

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 извлекает корень из кучи и вызывает heapify для изменения положения, помещая следующий элемент с самым высоким приоритетом в корень.

maxHeap.prototype.extractMax = function() {
	  // удаляем первый элемент из кучи
	  const root = this.heap.shift();
	 
	  // помещаем последний элемент перед кучей
	  // и удаляем последний элемент из кучи, так как он
	  // теперь размещен перед множеством
	  this.heap.unshift(this.heap[this.heap.length - 1]);
	  this.heap.pop();
	  
	  // корректно перестраиваем кучу
	  this.heapify(0);
	  
	  return root;
	}

Heapify

Метод Heapify перестраивает кучу, сравнивая левого и правого потомков определенного узла и меняя их местами. Метод вызывается рекурсивно, пока куча не будет перестроена правильно.

maxHeap.prototype.heapify = function(index) {
	  let left = leftChild(index);
	  let right = rightChild(index);
	  let smallest = index;
	
	  // если левый потомок больше, чем узел, который мы рассматриваем
	  if (left < this.heap.length && this.heap[smallest] < this.heap[left]) {
	    smallest = left;
	  }
	  
	  // если правый потомок больше, чем узел, который мы рассматриваем
	  if (right < this.heap.length && this.heap[smallest] < this.heap[right]) {
	    smallest = right;
	  }
	  
	  // если значение наименьшего элемента изменилось, нужно изменить его положение в куче
	  // и этот метод нужно вызвать снова с переставляемыми элементами
	  if (smallest != index) {
	    this.swap(smallest, index);
	    this.heapify(smallest);
	  }
	}

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

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

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

Анализ

• insert — O(log n)
• peek — O(1)
• extractMax/extractMin — O(log n)

Можете ли вы определить, почему верхние границы такие, какие они есть? Когда мы выполняем вставку, то сравниваем только половину дерева. Мы сравниваем значение приоритета новых элементов с его родителем рекурсивно, пока не доберемся до корня. При этом сравниваем их только один раз, следовательно, O(log n).

Извлечение равно O(log n), так как мы запускаем метод heapify во время этой операции, чтобы сохранить свойство heap.

Вывод и вызов

Теперь посмотрим, сможете ли вы создать минимальную кучу. Методы для обоих типов куч одинаковы, за исключением extractMax(). Это метод заменяется extractMin (). В минимальной куче наименьший элемент должен находиться в корне.