Приоритетная очередь

Класс Queue

Сбалансированное бинарное дерево позволяет быстро найти любой узел. Однако во многих приложениях требуется получать не произвольный узел, а только минимальный. Такая задача возникает, например, при организации направленного поиска. Подходящей для этого структурой данных будет приоритетная очередь (priority queue).

Прежде чем обсуждать детали организации приоритетной очереди, приведём пример её использования (модуль queue.js): 

var q = new Queue();                              // создаём пустую приоритетную очередь
for(var i = 0; i < 50; i++)                       // заталкиваем в неё 50 случайных чисел
   q.unshift(Math.floor(Math.random()*100));      // в диапазоне от 0 до 99

while( !q.empty() )                               // пока очередь не пустая,
   document.write(q.shift(), ", ");               // выталкиваем минимальный элемент
В этом примере в приоритетную очередь последовательно помещается 50 случайных чисел в диапазоне от 0 до 99. Затем в цикле while элементы из очереди выталкиваются в порядке увеличения их значения:

Кроме конструктора, в классе Queue есть 3 базовые функции: unshift(n) - добавление в очередь нового элемента n (сдвигая "назад" большие элементы), shift() - выталкивание минимального элемента (сдвигая очередь "вперёд") и, наконец, логическая функция empty() возвращающая true, если очередь пустая (иначе - false).

В приоритетной очереди можно сохранять не только числа или строки, но и любые объекты. Для этого необходимо переопределить функцию меньше: 

var q = new Queue();                              // создаём пустую приоритетную очередь
q.lt  = function(a,b) { return a.val < b.val; }   // функция меньше

q.unshift( {val:2,   item:"table"} );             // добавляем 4 объекта
q.unshift( {val:75,  item:"book" } );
q.unshift( {val:10,  item:"ring" } );
q.unshift( {val:5,   item:"car"  } );

while( !q.empty() ){                              // пока очередь не пустая,
   var n = q.shift();                             // выталкиваем объект с минимальным значением val
   document.write('{val:'+n.val+", item:"+n.item+"}, ");
}

Организация дерева очереди

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

Узлы дерева будем хранить в массиве ar. Корневой узел находится в элементе ar[1]. Его два потомка в ar[2] и ar[3]. Потомки i-того узла (элемента ar[i]) хранятся в ar[2*i] и ar[2*i+1]. Благодаря такой организации данных, бинарное дерево максимально сбалансировано. Если число узлов равно length = 2k-1, то в дереве будут заняты все листья на его нижнем (k-том) уровне. В общем случае, нижний уровень дерева заполняется слева направо и в ar[length] находится самый правый узел нижнего уровня. Нулевой элемент массива ar не используется. Ниже приведено бинарное дерево и соответствующее ему представление в виде массива (заметим, что элементы в массиве идут в порядке обхода дерева сверху-вниз и слева-направо):

i: 0 1 2 3 4 5 6 7 8 9 10
ar: - 0 1 4 3 2 7 9 8 5 6
Понятно, что родитель i-го узла - это элемент ar[i/2]. Напомним, что в JavaScript, в отличии от С++, целочисленного деления нет (все числа вещественные). Впрочем, быстрое целочисленное деление можно организовать при помощи логического сдвига на один бинарный разряд: i >> 1.

Констрктор класса Queue имеет вид: 

function Queue(num)
{
   if(!num) num = 1000;                           // по умолчанию максимум очереди = 1000
   this.ar   = new Array(num);                    // массив, хранящий узлы очереди
   this.length = 0;                               // число узлов в очереди
}
Массив для хранения узлов бинарного дерева очереди по умолчанию будет иметь 1000 элементов. JavaScript терпимо относится к выходу индекса за пределы длины массива. Если это происходит, его размер автоматически увеличивается. Однако, эта операция достаточно затратная по времени (необходимо выделить новую память, скопировать данные и освободить старую память). Поэтому при работе с очередью стоит зарезервировать массив по-больше.

Добавление элемента в очередь

Добавление - достаточно простая операция. Новый узел дерева сначала помещается в самый его низ. Для этого новый узел достаточно вставить за последним узлом в массиве (первая строка функции). Напомним, что, если ++ стоит перед переменной, то сначала она увеличивается на единицу (ниже это увеличение числа узлов ++this.length дерева), а затем участвует в выражении: 

Queue.prototype.unshift = function(n)
{
   this.ar[++this.length] = n;                    // добавляем узел
   for(var i=this.length; i > 1 && this.lt(this.ar[i], this.ar[i >> 1]); i = i >> 1)
      this.swap(i, i >> 1);                       // движемся вверх к корню
}
Оказавшись последним элементом массива, узел становится дочерним для узла с индексом length/2 === i >> 1 ("целочисленное деление"). Затем, его необходимо поднимать вверх по дереву к корню (переставляя с родительскими узлами местами) до тех пор, пока он меньше родителя. Для операции меньше по-умолчанию используется функция: 
Queue.prototype.lt = function (a, b){ return a < b; }
Функция перестановки i-того и j-того элементов массива ar имеет вид: 
Queue.prototype.swap = function (i, j)
{
   var a = this.ar[i]; this.ar[i] = this.ar[j]; this.ar[j] = a;
}

Ниже приведены последовательные действия по добавлению нового узла со значением 2 и его подъем вверх на положенное для него место:

Выталкивание элемента из очереди

Чтобы вытолкнуть минимальный элемент из очереди, необходимо проделать следующие действия. Сначала меняем местами корень и последний узел дерева. После этого, бывший корень (минимальный узел) можно без проблем удалить, уменьшив число узлов length--. Однако, бывший последний узел, оказавшись в корне, нарушает свойства дерева. Поэтому его необходимо опустить вниз, меняя с своими потомками местами, пока он не займёт "надлежащего" положения на дереве. Это произойдёт, когда оба его потомка окажутся большими или равными опускаемому узлу. При опускании, узел меняется с минимальным из двух потомков, чтобы выше поднялось меньшее значение. Ниже приведен пример, в котором вниз опускается ключ 5, после его обмена с корнем 1:

Соответствующий код функции shift имеет вид: 

Queue.prototype.shift = function()
{
   if(this.length===0)                            // очередь пустая
      return;                                     // вернём undefined

   this.swap(1, this.length);                     // переставляем корень в конец массива
   this.rebuild(1);                               // перестраиваем дерево
   return this.ar[this.length--];                 // уменьшаем число узлов
}
Она использует функцию "приведение в порядок" дерева, начиная с узла node и ниже: 
Queue.prototype.rebuild = function(node)
{
   var lf = 2*node;                               // левый наследник узла node
   if(lf < this.length){                          // если он есть (игнорируя бывший корень)
      var rt = lf + 1;                            // это правый наследник node
      if(rt < this.length && this.lt(this.ar[rt], this.ar[lf]) )
         lf = rt;                                 // выбираем наименьший (если rt есть)
      if( this.lt(this.ar[lf], this.ar[node]) ){  // если он меньше node
         this.swap(node, lf);                     // переставляем их местами
         this.rebuild(lf);                        // и повторяем операцию
      }
   }
}

Использование бинарной кучи - это самый простой способ организации приоритетной очереди. Для поддержки свойств кучи при вставке и выталкивании узла требуется в среднем log2N операций, где N - число узлов в дереве. За счёт некоторого усложнения, можно получить единичную сложность O(1) добавления (т.е. скорость добавления не зависит от числа узлов). При этом сохраняется логарифмическая сложность удалении узла. Соответствующая структура данных называется кучей Фибоначчи.

Обратим внимание, что приоритетная очередь одновременно является способом сортировки (некоторая совокупность величин помещается в очередь, откуда извлекается уже в заданном порядке).