Приоритетная очередь
Класс 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(), ", " ); // выталкиваем минимальный элемент |
Кроме конструктора, в классе 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 не используется. Ниже приведено бинарное дерево и соответствующее ему представление в виде массива (заметим, что элементы в массиве идут в порядке обхода дерева сверху-вниз и слева-направо):
Констрктор класса Queue имеет вид:
function Queue(num) { if (!num) num = 1000; // по умолчанию максимум очереди = 1000 this .ar = new Array(num); // массив, хранящий узлы очереди this .length = 0; // число узлов в очереди } |
Добавление элемента в очередь
Добавление - достаточно простая операция. Новый узел дерева сначала помещается в самый его низ. Для этого новый узел достаточно вставить за последним узлом в массиве (первая строка функции). Напомним, что, если ++ стоит перед переменной, то сначала она увеличивается на единицу (ниже это увеличение числа узлов ++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); // движемся вверх к корню } |
Queue. prototype .lt = function (a, b){ return a < b; } |
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--]; // уменьшаем число узлов } |
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) добавления (т.е. скорость добавления не зависит от числа узлов). При этом сохраняется логарифмическая сложность удалении узла. Соответствующая структура данных называется кучей Фибоначчи.
Обратим внимание, что приоритетная очередь одновременно является способом сортировки (некоторая совокупность величин помещается в очередь, откуда извлекается уже в заданном порядке).