Приоритетная очередь.
Данная структура данных широко используется в различных задачах. Одно из самых важных ее применений - алгоритм Дейкстры.
В общем случае приоритетная очередь - это структура данных, которая хранит набор пар (ключ - значение) и поддерживает следующие операции:
1) Object min();
Возвращает значение элемента с минимальным ключом.
2) void insert(Comparable key, Object value);
Вставляет в очередь пару (key - value). Обратите внимание, что ключ обязательно должен поддерживать сравнение, что, в принципе, логично.
3) void removeMin();
Удаляет элемент с минимальным ключом.
Наиболее оптимальной реализацией приоритетной очереди считается двоичная куча (binary heap).
Основные свойства BinaryHeap:
1) Это полное бинарное дерево (то есть бинарное дерево, в котором заполнены все уровни, кроме, возможно, последнего)
2) Это дерево обладает свойством кучи, то есть ни один потомок не может быть меньше своего предка (стало быть, корнем всегда является элемент с наименьшим ключом).
Свойство полноты позволяет нам представить BinaryHeap в виде массива. Пример:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 2 5 4 6 7 8 9 17 10 12 - - - -
Здесь элемент с индексом 1 - корень. Детьми i'го элемента являются элементы 2*i и 2*i+1. Родителем i'го элемента является элемент с индексом i/2 (корень не имеет родителя).
Рассмотрим реализацию операций с кучей.
1) Object min();
Очень просто - вернуть элемент с индексом 1, то есть корень. Корень всегда имеет минимальный ключ.
2) void insert(Comparable key, Object value);
Чуть сложнее. Сначала вставляем новую запись на первое свободное место (первое пустое место в массиве, не считая 0). Далее запускаем цикл:
Х = индекс вставленного элемента
Пока ((Х имеет родителя) И (родитель имеет меньший ключ нежели Х)) обменять местами элемент по индексу Х и родителя, Х/=2
Пример: вставим в исходную очередь (см. выше) элемент с ключом 3.
Шаг 1:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 2 5 4 6 7 8 9 17 10 12 3 - - -
Шаг 2:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 2 5 4 6 3 8 9 17 10 12 7 - - -
Шаг 3:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 2 3 4 6 5 8 9 17 10 12 7 - - -
Все, новый элемент вставлен.
3) void removeMin();
Удаляем корень дерева. Ставим на его место последний лист дерева. Запускаем цикл:
Х = 1
Пока ((Х имеет хотя бы одного потомка) И (хотя бы один из потомков имеет ключ < ключа элемента Х)) поменять местами элемент по индексу Х и его ребенка с МЕНЬШИМ ключом, Х = индекс этого ребенка
Пример: удалим из исходной очереди элемент с наименьшем ключом.
Шаг 1:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - - 5 4 6 7 8 9 17 10 12 - - - -
Шаг 2:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 12 5 4 6 7 8 9 17 10 - - - - -
Шаг 3:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 4 5 12 6 7 8 9 17 10 - - - - -
Шаг 4:
индекс 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
ключ - 4 5 8 6 7 12 9 17 10 - - - - -
Все, элемент удален.
Оценки алгоритмов (в тета-нотации, среднее время):
min() - O(1)
insert - O(log n)
removeMin - O(log n)
Все выше написанное является вольной интерпретацией Кнута и этой замечательной лекции:
http://www.youtube.com/watch?v=yIUFT6AK … p;index=23
(ЭТО ПЕАР!)
Моя реализация:
class PQueue{
private static final int MAX = 1100000;
private class Entry{
Comparable key;
Object value;
Entry() {}
Entry(Comparable _k, Object _val){
key=_k;
value=_val;
}
}
private Entry[] arr = new Entry[MAX+1];
private int sz = 0;
public boolean empty(){
return sz==0;
}
public Object min()throws Exception{
if(sz==0)
throw new Exception("Empty queue!");
return arr[1].value;
}
public void insert(Comparable key, Object value)throws Exception{
if(sz==524288)
throw new Exception("Overflow!");
arr[++sz]= new Entry(key,value);
int ind = sz;
while(ind>1){
if(arr[ind].key.compareTo(arr[ind/2].key)<0){
Entry tmp=arr[ind];
arr[ind]=arr[ind/2];
arr[ind/2]=tmp;
ind/=2;
}
else
break;
}
}
public void removeMin() throws Exception{
if(sz==0)
throw new Exception ("Empty queue!");
arr[1]=null;
if(sz==1){
sz=0;
return;
}
arr[1]=arr[sz];
arr[sz--]=null;
int ind=1;
while((arr[2*ind]!=null && arr[2*ind].key.compareTo(arr[ind].key)<0) || (arr[2*ind+1]!=null && arr[2*ind+1].key.compareTo(arr[ind].key)<0)){
if(arr[2*ind]==null){
Entry tmp=arr[ind];
arr[ind]=arr[2*ind+1];
arr[2*ind+1] = tmp;
break;
}
if(arr[2*ind+1]==null){
Entry tmp=arr[ind];
arr[ind]=arr[2*ind];
arr[2*ind] = tmp;
break;
}
if(arr[2*ind].key.compareTo(arr[2*ind+1].key)<0){
Entry tmp=arr[ind];
arr[ind]=arr[2*ind];
arr[2*ind] = tmp;
ind=ind*2;
}
else{
Entry tmp=arr[ind];
arr[ind]=arr[2*ind+1];
arr[2*ind+1] = tmp;
ind=ind*2+1;
}
}
}
}Отредактировано Ikari (2009-01-08 16:33:24)
: