Implementation and Visualization Binary Heap
二分ヒープを実装しました。
機能
| 操作 | 最悪計算量 |
|---|---|
| 最大（最小）値の取得 | $O(1)$ |
| 要素の挿入 | $O(\log_2 n)$ |
| 最大（最小）値を持つ要素の削除 | $O(\log_2 n)$ |
$n$はヒープの要素数です。
実装
up-heapは簡単だけど、down-heapは子が2つある場合優先度の高いほうと比較しないといけないことに注意します。
ベンチマーク
方法
- $10^5$回要素を挿入
- $10^5/2$回最大値を持つ要素を削除
- $10^5$回要素を挿入
- $10^5/2$回最大値を持つ要素を削除
挿入する要素は$[-10^9, 10^9)$の範囲の整数をランダムに選びます。
環境
dmd --version DMD64 D Compiler v2.081.2
コンパイルオプションは -O -release -inline
結果
| std.container.binaryheap.BinaryHeap | 1 sec 552 ms |
| std.container.rbtree.RedBlackTree | 7 secs 480 ms |
| myBinaryHeap | 2 secs 265 ms |
検証用のソースコード
ビジュアライザ
https://ia7ck.github.io/visualization/binary-heap
