Модуль Pqueue

module Pqueue: sig .. end

Очереди с приоритетом.

Модуль Pqueue реализует структуру данных «очередь с приоритетом» для типа элементов с полным порядком. Эта структура данных является изменяемой. Реализованы очереди с минимальным и максимальным приоритетом.

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

В очереди могут находиться несколько элементов с одинаковым приоритетом. Порядок их извлечения не гарантируется. Однако гарантируется, что элемент, возвращённый min_elt (или get_min_elt), — это именно тот элемент, который удаляется из очереди с приоритетом с помощью pop_min (или remove_min). Это важно для многих алгоритмов (например, когда нужно просмотреть несколько очередей с приоритетом, а затем выбрать одну из них для удаления элемента).

Начиная с версии 5.4

module type OrderedType = sig .. end

Входная сигнатура функторов Pqueue.MakeMin и Pqueue.MakeMax.

module type Min = sig .. end

Выходная сигнатура функтора Pqueue.MakeMin.

module MakeMin: functor (E : OrderedType) -> Min  with type elt := E.t

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

module type Max = sig .. end

Выходная сигнатура функтора Pqueue.MakeMax.

module MakeMax: functor (E : OrderedType) -> Max  with type elt := E.t

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

Полиморфные очереди с приоритетом

Следующие, более сложные функторы создают полиморфные очереди типа 'a t, подобно другим полиморфным контейнерам (спискам, массивам и т. д.). Для этого им требуется понятие «полиморфных элементов» 'a elt, которые можно сравнивать независимо от значений 'a.

Один из вариантов использования — передача приоритетов отдельно от значения, хранящегося в очереди. Для этого в качестве элементов используются пары priority * 'a.

      module Prio : OrderedType = ...

      module PrioQueue = Pqueue.MakeMinPoly(struct
        type 'a t = Prio.t * 'a
        let compare (p1, _) (p2, _) = Prio.compare p1 p2
      end)

      (* for example, we now have: *)
      PrioQueue.add: 'a PrioQueue.t -> Prio.t * 'a -> unit
      PrioQueue.min_elt: 'a PrioQueue.t -> (Prio.t * 'a) option

module type OrderedPolyType = sig .. end

Входная сигнатура функторов Pqueue.MakeMinPoly и Pqueue.MakeMaxPoly.

module type MinPoly = sig .. end

Выходная сигнатура функтора Pqueue.MakeMinPoly.

module MakeMinPoly: functor (E : OrderedPolyType) -> MinPoly  with type 'a elt := 'a E.t

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

module type MaxPoly = sig .. end

Выходная сигнатура функтора Pqueue.MakeMaxPoly.

module MakeMaxPoly: functor (E : OrderedPolyType) -> MaxPoly  with type 'a elt := 'a E.t

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