heapqueue

heapqueue モジュールは優先順位付きキューとして使えるヒープによるデータ構造の実装です。ヒープは a[k] <= a[2*k+1]k に関する a[k] <= a[2*k+2] の配列がすべてあり、要素は 0 から数えます。ヒープの興味深い性質として a[0] は必ず最小要素になることです。

基本の用法

import heapqueue

var heap = initHeapQueue[int]()
heap.push(8)
heap.push(2)
heap.push(5)
# 最初の要素は最下位の要素です
assert heap[0] == 2
# 最下位の要素を削除して返します
assert heap.pop() == 2
# 最下位の要素には 5 が残存します
assert heap[0] == 5

カスタムオブジェクトの用法

カスタムオブジェクトで HeapQueue を使うには、 < 演算子を実装してください。

import 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

HeapQueue[T] = object
  data: seq[T]
一般にヒープキューは、優先順位付きキューとしても知られています。  ソース 編集

プロシージャ

proc initHeapQueue[T](): HeapQueue[T]
空のヒープを新規作成します。  ソース 編集
proc len[T](heap: HeapQueue[T]): int {...}{.inline.}
heap の要素数を返します。  ソース 編集
proc `[]`[T](heap: HeapQueue[T]; i: Natural): T {...}{.inline.}
heap の i 番目にある要素へアクセスします。  ソース 編集
proc push[T](heap: var HeapQueue[T]; item: T)
ヒープの不変量を持続したまま、ヒープへ item を push (プッシュ、退避) します。  ソース 編集
proc pop[T](heap: var HeapQueue[T]): T
ヒープの不変量を持続したまま、 heap から最小アイテムを pop (ポップ、復帰) して返します。  ソース 編集
proc del[T](heap: var HeapQueue[T]; index: Natural)
ヒープの不変量を持続したまま、 heap から index で指定された要素を削除します。  ソース 編集
proc replace[T](heap: var HeapQueue[T]; item: T): T
現在の最小値を pop (ポップ、復帰) して返してから、新しいアイテムを追加します。これは push() の後に pop() をするよりも効率的であり、固定サイズのヒープを使うよりも適切です。返された値はアイテムよりも大きい場合があることに注意してください。このルーチンを使うにあたって条件付き置換の一部が記述されていないならば合理的な制約が課せられます:
if item > heap[0]:
    item = replace(heap, item)
  ソース 編集
proc pushpop[T](heap: var HeapQueue[T]; item: T): T
push の高速版です。続けて pop を行います。  ソース 編集
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]"
  ソース 編集
proc newHeapQueue[T](): HeapQueue[T] {...}{.deprecated: "Deprecated since v0.20.0: use \'initHeapQueue\' instead.".}
廃止: v0.20.0 以降で廃止: 'initHeapQueue' をお使いください。
  ソース 編集
proc newHeapQueue[T](heap: var HeapQueue[T]) {...}{.
    deprecated: "Deprecated since v0.20.0: use \'clear\' instead.".}
廃止: v0.20.0 以降で廃止: 'clear' をお使いください。
  ソース 編集