heapqueue

Модуль heapqueue реализует структуру данных кучу, которая может использоваться в качестве приоритетной очереди. Кучи представляют собой массивы, для которых a[k] <= a[2*k+1] и a[k] <= a[2*k+2] для всех k, считая элементы с 0. Интересное свойство кучи состоит в том, что a[0] всегда является её наименьшим элементом.

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

Пример:

var heap = initHeapQueue[int]()
heap.push(8)
heap.push(2)
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 с пользовательским объектом необходимо реализовать оператор <.

Пример:

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
  data: seq[T]

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

Процедуры

proc initHeapQueue[T](): HeapQueue[T]

Создаёт новую пустую кучу.

См. также:

• Процедуру toHeapQueue

Исходный код Изменить

proc len[T](heap: HeapQueue[T]): int {...}{.inline.}

Возвращает количество элементов в heap. Исходный код Изменить

proc `[]`[T](heap: HeapQueue[T]; i: Natural): lent T {...}{.inline.}

Доступ к i-му элементу heap. Исходный код Изменить

proc push[T](heap: var HeapQueue[T]; item: sink T)

Добавляет item в кучу, сохраняя её инвариант. Исходный код Изменить

proc toHeapQueue[T](x: openArray[T]): HeapQueue[T]

Создаёт новую HeapQueue, содержащую элементы x.

См. также:

• Процедуру initHeapQueue

Пример:

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

Исходный код Изменить

proc pop[T](heap: var HeapQueue[T]): T

Извлекает и возвращает наименьший элемент из heap, сохраняя инвариант кучи.

Пример:

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

Исходный код Изменить

proc find[T](heap: HeapQueue[T]; x: T): int

Линейный поиск для нахождения индекса элемента x или -1, если он не найден.

Пример:

var heap = toHeapQueue([9, 5, 8])
assert heap.find(5) == 0
assert heap.find(9) == 1
assert heap.find(777) == -1

Исходный код Изменить

proc del[T](heap: var HeapQueue[T]; index: Natural)

Удаляет элемент по индексу index из heap, сохраняя инвариант кучи.

Пример:

var heap = toHeapQueue([9, 5, 8])
heap.del(1)
assert heap[0] == 5
assert heap[1] == 8

Исходный код Изменить

proc replace[T](heap: var HeapQueue[T]; item: sink T): T

Извлекает и возвращает текущее наименьшее значение, а затем добавляет новый элемент. Это более эффективно, чем pop() и затем push(), и может быть более подходящим при использовании кучи с фиксированным размером. Обратите внимание, что возвращаемое значение может быть больше, чем item! Это ограничивает разумное использование этой функции, если она не написана как часть условной замены:

Пример:

var heap = initHeapQueue[int]()
heap.push(5)
heap.push(12)
assert heap.replace(6) == 5
assert heap.len == 2
assert heap[0] == 6
assert heap.replace(4) == 6

Исходный код Изменить

proc pushpop[T](heap: var HeapQueue[T]; item: sink T): T

Быстрая версия push, за которой следует pop.

Пример:

var heap = initHeapQueue[int]()
heap.push(5)
heap.push(12)
assert heap.pushpop(6) == 5
assert heap.len == 2
assert heap[0] == 6
assert heap.pushpop(4) == 4

Исходный код Изменить

proc clear[T](heap: var HeapQueue[T])

Удаляет все элементы из heap, делая её пустой.

Пример:

var heap = initHeapQueue[int]()
heap.push(1)
heap.clear()
assert heap.len == 0

Исходный код Изменить

proc `$`[T](heap: HeapQueue[T]): string

Преобразует кучу в строковое представление.

Пример:

var heap = initHeapQueue[int]()
heap.push(1)
heap.push(2)
assert $heap == "[1, 2]"

Исходный код Изменить