Расширение очереди по приоритету

Расширение очереди по приоритету

Сделав небольшое отступление для ознакомления с пирамидальной сортировкой, пора вернуться к очередям по приоритету и рассмотреть задачу расширения реализованной нами структуры данных.

Мы разработали структуру данных, позволяющую выполнять две основные операции: постановку в очередь, обеспечивающую добавление элемента в структуру, и исключение из очереди, которая возвращает элемент структуры с наивысшим приоритетом (попутно мы рассмотрели определение приоритета за счет использования внешней функции сравнения). Полученную структуру мы назвали очередью по приоритету.

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

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

На первый взгляд, реализация этих операций за счет использования сортирующего дерева может показаться затруднительной. Однако рассмотрим проблему подробнее. Классу очереди по приоритету нужно было бы передать ссылку на элемент, расположенный где-то в очереди, чтобы его можно было удалить или изменить его приоритет. Как найти элемент в очереди? Это один из тех случаев, когда "свободная" сортировка сортирующего дерева работает против нас. Единственным возможным методом поиска на этом этапе кажется последовательный поиск, но он выполняется достаточно медленно. После того как элемент найден, мы должны либо удалить его, либо изменить его приоритет, а затем восстановить полноту или пирамидальность сортирующего дерева, либо же оба свойства.

Восстановление свойства пирамидальное

Вторую проблему (восстановление свойства пирамидальности) проще решить, чем первую (отыскание элемента, который нужно удалить или изменить его приоритет). Поэтому вначале рассмотрим именно ее.

Чтобы удалить произвольный элемент из сортирующего дерева, его нужно было бы поменять местами с последним элементом и уменьшить размер сортирующего дерева. На этом этапе появляется элемент, который может нарушить свойство пирамидальности.

Для изменения приоритета произвольного элемента следует просто внести изменение, в результате чего элемент может также нарушить свойство пирамидальности.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Расширение OCB

Из книги автора

Расширение OCB В ряде случаев у вас может возникнуть необходимость расширения OCB. Процедура эта является относительно безболезненной. Обычно OCB расширяют дополнительными флагами, характеризующими каждый конкретный open(). Один такой флаг можно было бы использовать с


Javascript — это расширение

Из книги автора

Javascript — это расширение Мы используем JavaScript, только чтобы улучшить уже существующую функциональность, так как мы не можем на него полностью полагаться. JavaScript может быть выключен или отфильтрован прокси-серверами и файерволлами компаний, обеспечивающих безопасность. Мы


Расширение кругозора

Из книги автора

Расширение кругозора Профессиональные программисты часто страдают от однообразия решаемых задач. Работодатели часто ограничиваются одним языком, платформой и предметной областью, в которой должен работать программист. Если вы не позаботитесь о расширении


Расширение

Из книги автора

Расширение Расширяя свое укрытие, вы можете добавить комнату для карт, пристань для лодок и рыбалки, фермы и башню для обзора. Для дополнительной защиты вы можете оградить свой дом массивной каменной стеной. Неплохо будет построить ферму мобов рядом с домом.


4.9. Расширение прав

Из книги автора

4.9. Расширение прав Регламентация доступа — достаточно сложный процесс. Это основная задача администратора и от правильности ее выполнения зависит многое. Любая ошибка может стоить вам зарплаты и благополучия. В мире, когда информация является самым дорогим продуктом,


14.5.2. Расширение Win32OLE

Из книги автора

14.5.2. Расширение Win32OLE Расширение Win32OLE (правильно писать его имя строчными буквами: win32ole) реализует интерфейс к OLE-автоматизации в Windows. Программа на Ruby может выступать в роли клиента любого сервера автоматизации, к числу которых относятся, например, Microsoft Word, Outlook, Internet Explorer,


Глава 9. Очереди по приоритету и пирамидальная сортировка.

Из книги автора

Глава 9. Очереди по приоритету и пирамидальная сортировка. В главе 3 мы рассмотрели несколько очень простых структур данных. Одной из них была очередь. В эту структуру можно было добавлять элементы, а затем извлекать их в порядке поступления. При этом сохранение даты и


Очередь по приоритету

Из книги автора

Очередь по приоритету Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с


У6.10 Очереди

Из книги автора

У6.10 Очереди Описать в виде АТД очереди (первым пришел - первым ушел) в том же стиле, что и стеки. Обратите внимание на общие и отличительные черты этих АТД. (Указание: аксиомы для item и remove должны отличаться, при описании put (s,x) рассмотрите случаи, когда очередь s пуста и


Расширение ("Expand")

Из книги автора

Расширение ("Expand") Этот эффект заставляет выделенный фрагмент изображения постепенно "вырастать" или "съеживаться", в зависимости от заданных нами параметров.Чтобы применить этот эффект к выделенному фрагменту изображения, нужно выбрать пункт Expand подменю Effects подменю