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

0

Расширить возможности очереди с приоритетами, реализованной с помощью последовательности или пирамиды, за счет поддержки локаторов не представляет особого труда. В частности, за счет преимущества наследования, помня о том, что последовательность и бинарное дерево являются позиционными контейнерами и могут использоваться для реализации АТД «очередь с приоритетами», можно сортировать пары «ключ-элемент» (объекты) как элементы. Соответственно можно создать локатор, расширив объект «ключ-элемент» из фрагмента кода 7.2 для реализации локатор- ного АТД и добавив позиционную ссылку в качестве переменной экземпляра, как это показано во фрагменте кода 7.9. При таком подходе реализация методов локаторного АТД достаточно проста, и каждая занимает 0(1) времени. Наиболее значимым фактом такой реализации является автома- тическсЪприсоединение локаторов к объектам (по существу, локаторы сохраняют объекты), и необходима отслеживать позиции, в которых размещаются объекты в последовательности или пирамиде.

public class Item2 extends Item Implements Locator { private Position pos; Item2 (Object k, Object e, Position p) { super(k, e);

pos = p;

}

protected Position position() {return pos; } protected void setPosition(Position p) { pos = p; }

}

Фрагмент кода 7.9. Класс Item2, использующий локаторы для реализации очереди с приоритетами с помощью сортированной последовательности

В табл. 7.3 сравнивается время выполнения методов АТД «очередь с приоритетами», описанных в этом разделе и в п. 7.1.3.

Метод

Несортированная последовательность

Сортированная после довател ьн ость

Пирамида

size, isEmpty, key, replaceElement

0(1)

0(1)

0(1)

minElement, min, minKey

0(л)

0(1)

0(1)

insertltem, insert

0(1)

0(л)

0(log п)

removeMin

0(n)

0(1)

0(log 77)

remove

0(1)

0(1)

0(log п)

replaceKey

0(1)

0(л)

0(log ri)

Таблица 7.3. Сравнение времени выполнения методов АТД «очередь с приоритетами» для реализаций с помощью несортированной и сортированной последовательностей и пирамиды. Здесь п обозначает количество элементов в очереди с приоритетами во время выполнения метода

Во фрагментах кода 7.10 и 7.11 показана Java-реализация очереди с приоритетами, поддерживающая локаторные методы. Реализация получена в результате расширения класса SortedSequencePriorityQueue из фрагмента кода 7.4.

public class SortedSequencePriorityQueue2

extends SortedSequencePriorityQueue implements PriorityQueue2 { public SortedSequencePriorityQueue2 (Comparator comp) { super(comp);

}

protected Locator loclnsert(ltem2 locitem) throws InvalidKeyException

{

Position p, curr; Object k = locitem. key(); if (komp.isComparable(k))

throw new lnvalidKeyException("The key is not valid"); else

if (S.isEmptyO)

p = S.insertFirst(locitem); else if (comp.isGreaterThan(k, key(S.lastQ)))’

p = S.insertAfter(S.last(),locitem); else {

curr = S.first();

while (comp.isGreaterThan(k, key(curr)))

curr = S.after(curr); p = S.insertBefore(curr,locitem);

}

Locitem/$etPosition(p); return (Locator) locitem;

protected Item2 locRemove(Locator loc) { S.remove(((ltem2) loc).position()); return (Item2) loc;

}

Фрагмент кода 7.10. Реализация локаторных методов сортировки очереди с приоритетами на основе применения сортированной последовательности. Класс SortedSequencePriorityQueue2 расширяет класс SortedSequencePriorityQueue (фрагмент кода 7.4) и реализует Java-интерфейс PriorityQueue2, содержащий локаторные методы АТД «очередь с приоритетами», представленные в п. 7.4.1 (продолжение — фрагмент кода 7.11)

public Locator min () throws PriorityQueueEmptyException { if (S.isEmptyO)

throw new PriorityQueueEmptyExceptipn("The priority queue is empty"); else

return (Locator) S.first().element();

}

public void insert(Locator loc) throws InvalidKeyException { loclnsert((ltem2) loc);

}

public Locator insert(Object k, Object e) throws InvalidKeyException { Item2 locitem = new Item2(k, e, null); return loclnsert(locitem);

}

public void insertltem (Object k, Object e) throws InvalidKeyException { insert(k, e);

}

public void remove(Locator loc) { locRemove(loc);

}

public Object removeMin () throws PriorityQueueEmptyException { Object toReturn = minElement(); remove(min()).; return toReturn;

}

public Object replaceElement (Locator loc, Object newElement) { Object oldElement = ((Item2) loc).element(); ((Item2) loc).setElement(newElement); return oldElement;

}

public Object replaceKey(Locator loc, Object newKey)

throws InvalidKeyException { Item2 locitem = locRemove(loc); Object oldKey = ((Item2) loc).key(); locitem.setKey(newKey); loclnsert(locitem);

return oldKey; }

}

Фрагмент кода 7.11. Реализация очереди с приоритетами, поддерживающей ло- каторные методы с помощью сортированной последовательности (продолжение фрагмента кода 7.10)

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

По теме:

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