C#. Очередь с приоритетами на бинарной пирамиде

Git

В данном разделе рассмотрим теорию из Сейджвика про очередь с приоритетами и бинарную пирамиду. Последнюю используем в качестве структуры данных для реализации очереди с приоритетами.

В данном случае напишем очередь, которая поддерживает

  • вставку элемента
  • получение элемента с максимальным ключом

Идея алгоритма в том, что в качестве бинарной пирамиды мы будем использовать массив. В этот массив мы будем вставлять данные и получать их из него. При каждой вставке, получении, целостность пирамиды у нас будет возможно нарушаться, поэтому мы будем частично обходить пирамиду для восстановления целостности. Такой обход будет стоить логарифмического времени.  Что позволит работать с огромными данными.

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

<

Используя эти знания, напишем класс очереди с приоритетами, используя в качестве структуры данных бинарную пирамиду. Основное его назначение – функции Insert и DelMax.

DelMax будет доставать максимальный элемент из очереди и удалять его из очереди.

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

MaxPQ класс

Аналогично MinPQ

 

Клиент тестирования будет выглядеть так…

 

This entry was posted in C#. Bookmark the permalink.