Главная » Java, Структуры данных и алгоритмы » Реализация очередь с приоритетами на Java

0

Реализация на Java очереди с приоритетами с помощью пирамиды представлена фрагментами кода 7.5—7.7. Для обеспечения модульного принципа построения введем новую структуру данных под названием «пирамидальное дерево» (heap-tree), расширяющую свойства бинарного дерева и реализующую следующие дополнительные методы обновления:

add(o): выполняет следующую последовательность операций: expandExternal(^) replaceElement(^) return z\

таким образом, что z становится последним узлом дерева.

Input: объект о; Output: позиция.

remove(): выполняет следующую последовательность операций: t <г- z.element()

removeAboveExternal(rightChild(^)) return /;

где z — последний узел до начала операции.

Input: отсутствует; Output: объект.

Это значит, что операция add добавляет новый элемент в первый простой узел, а операция remove удаляет элемент из последнего узла. При использовании векторной реализации дерева (п. 6.4.1) операции добавления и удаления занимают 0(1) времени. АТД «пирамидальное дерево» представлен java-интерфейсом НеарТгее, показанным во фрагменте кода 7.5. Java-KJiacc VectorHeapTree (не показан) реализует интерфейс НеарТгее, методы add и remove которого выполняются за 0(1) времени.

public interface HeapTree extends InspectableBinaryTree,

PositionalContainer {

public Position add(Object elem); public Object remove();

}

Фрагмент кода 7.5. Интерфейс HeapTree для структуры пирамидального дерева. Наследует интерфейс InspectableBinaryTree и дополнительно использует методы replaceElement и swapElements, наследуемые из интерфейса PositionContainer, добавляет специализированные методы обновления add и remove

Класс HeapPriorityQueue реализует интерфейс PriorityQueue с помощью пирамиды. Он показан во фрагментах кода 7.6 и 7.7. Заметим, что пары «ключ-элемент» класса Item (см. фрагмент кода 1.2) сохраняются в heap-tree (пирамидальном дереве).

public class HeapPriorityQueue implements PriorityQueue { HeapTree T; Comparator comp;

public HeapPriorityQueue(Comparator c) { if ((comp = c) == null)

throw new NlegalArgumentException("Null comparator passed"); T = new VectorHeapTree();

}

public int size() {

return (T.size() – 1) / 2;

}

public boolean isEmptyO { return T.size() == 1; }

public Object minElement() throws PriorityQueueEmptyException { if (isEmptyO)

throw new PriorityQueueEmptyExceptionfEmpty Priority Queue"), return element(T.root());

}

public Object minKey() throws PriorityQueueEmptyException { if (isEmptyO)

throw new PriorityQueueEmptyException("Empty Priority Queue"); return key(T.root());

}

Фрагмент кода 7.6. Переменные экземпляров, конструктор и методы size, isEmpty, minElement и minKey класса HeapPriorityQueue, реализующего очередь с приоритетами с помощью пирамиды. Остальные методы класса показаны во фрагменте кода 7.7. Вспомогательные методы key и element извлекают из очереди пару «ключ-элемент», хранящуюся в определенной позиции пирамидального дерева

public void insertltem(Object k, Object e) throws InvalidKeyException { if (!comp.isComparable(k))

throw new lnvalidKeyException("Invalid Key"); Position z = T.add(new ltem(k, e)); Position u;

while (!T.isRoot(z)) { // восходящая сортировка u = T.parent(z);

if (comp.isLessThanOrEqualTo(key(u), key(z)))

break; T.swapElements(u, z); z = u;

}

}

public Object removeMin() throws PriorityQueueEmptyException { if (isEmpty())

throw new PriorityQueueEmptyException("Empty priority queue!"); Object min == element(T.root()); if (size() == 1) T.remove(); else {

T.replaceElement(T.root(), T.remove()); Position r = T.root();

while (T.islnternal(T.leftChild(r))) {// нисходящая сортировка Position s;

if (T.isExternal(T.rightChild(r)) II

comp.isLessThanOrEqualTo(key(T.leftChild(r)), key(T.rightChild(r))))

s = T.leftChild(r); else

s = TrightChild(r); if (comp.isLessThan(key(s), key(r))) { T.swapElements(r, s);

r = s;

}

else break;

}

}

return min;

}

Фрагмент кода 7.7. Методы insertltem и removeMin класса HeapPriorityQueue. Остальные методы класса показаны во фрагменте кода 7.6

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии