std/heapqueue

Source Edit

The heapqueue module implements a двоичная куча data structure that can be used as a очередь с приоритетами. They are represented as arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all indices k (counting elements from 0). The interesting property of a heap is that a[0] is always its smallest element.

Основные использование

Пример:

import std/heapqueue
var heap = [8, 2].toHeapQueue
heap.push(5)
# the first element is the lowest element
assert heap[0] == 2
# remove and return the lowest element
assert heap.pop() == 2
# the lowest element remaining is 5
assert heap[0] == 5

Использование с пользовательскими объектами

Для использования HeapQueue с пользовательским объектом, необходимо реализовать оператор <.

Пример:

import std/heapqueue
type Job = object
  priority: int

proc `<`(a, b: Job): bool = a.priority < b.priority

var jobs = initHeapQueue[Job]()
jobs.push(Job(priority: 1))
jobs.push(Job(priority: 2))

assert jobs[0].priority == 1

Импорты

since

Типы

HeapQueue[T] = object: Куча, обычно известная как очередь с приоритетами. Source Edit

Процедуры

proc `$`[T](heap: HeapQueue[T]): string: Преобразует кучу в её строковое представление.
Пример:

let heap = [1, 2].toHeapQueue assert $heap == "[1, 2]"
Source Edit
proc `[]`[T](heap: HeapQueue[T]; i: Natural): lent T {.inline.}: Доступ к i-му элементу heap. Source Edit
proc clear[T](heap: var HeapQueue[T]): Удаляет все элементы из heap, делая её пустой.
Пример:

var heap = [9, 5, 8].toHeapQueue heap.clear() assert heap.len == 0
Source Edit
proc contains[T](heap: HeapQueue[T]; x: T): bool: Возвращает true, если x находится в heap, или false, если не найдено. Это сокращение для find(heap, x) >= 0. Source Edit
proc del[T](heap: var HeapQueue[T]; index: Natural): Удаляет элемент в index из heap, сохраняя инвариант кучи.
Пример:

var heap = [9, 5, 8].toHeapQueue heap.del(1) assert heap[0] == 5 assert heap[1] == 8
Source Edit
proc find[T](heap: HeapQueue[T]; x: T): int: Линейный поиск индекса элемента x или -1, если не найден.
Пример:

let heap = [9, 5, 8].toHeapQueue assert heap.find(5) == 0 assert heap.find(9) == 1 assert heap.find(777) == -1
Source Edit
proc initHeapQueue[T](): HeapQueue[T]: Создаёт новую пустую кучу.

Кучи инициализируются по умолчанию, поэтому вызов этой функции не обязателен.

См. также:

процедура toHeapQueue

Source Edit
proc len[T](heap: HeapQueue[T]): int {.inline.}: Возвращает количество элементов в heap.
Пример:

let heap = [9, 5, 8].toHeapQueue assert heap.len == 3
Source Edit
proc pop[T](heap: var HeapQueue[T]): T: Извлекает и возвращает наименьший элемент из heap, сохраняя инвариант кучи.
Пример:

var heap = [9, 5, 8].toHeapQueue assert heap.pop() == 5
Source Edit
proc push[T](heap: var HeapQueue[T]; item: sink T): Добавляет item в heap, сохраняя инвариант кучи. Source Edit
proc pushpop[T](heap: var HeapQueue[T]; item: sink T): T: Быстрая версия push() с последующим pop().

См. также:

процедура replace

Пример:

var heap = [5, 12].toHeapQueue assert heap.pushpop(6) == 5 assert heap.len == 2 assert heap[0] == 6 assert heap.pushpop(4) == 4
Source Edit
proc replace[T](heap: var HeapQueue[T]; item: sink T): T: Извлекает и возвращает текущее наименьшее значение и добавляет новый элемент. Это более эффективно, чем pop() с последующим push(), и может быть более подходящим при использовании кучи фиксированного размера. Обратите внимание, что возвращаемое значение может быть больше, чем item! Это ограничивает разумное использование данной функции, если она не используется в условной замене.

См. также:

процедура pushpop

Пример:

var heap = [5, 12].toHeapQueue assert heap.replace(6) == 5 assert heap.len == 2 assert heap[0] == 6 assert heap.replace(4) == 6
Source Edit
proc toHeapQueue[T](x: openArray[T]): HeapQueue[T]: Создаёт новую HeapQueue, содержащую элементы x.

См. также:

процедура initHeapQueue

Пример:

var heap = [9, 5, 8].toHeapQueue assert heap.pop() == 5 assert heap[0] == 8
Source Edit

Итераторы

iterator items[T](heap: HeapQueue[T]): lent T {.inline.}: Итерируется по каждому элементу heap. Source Edit