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
数独をプログラムで解く
数独（SUDOKU)をプログラム (Ruby) で解きます。
アルゴリズム
マスを前から見ていって、空欄のマスに1, 2, ..., 9の順で置けるかどうか試します。
- 置けるならその数字を置いて次のマスを見る
- どの数字も置けないなら、いままでの数字の置き方がまずかったということなので前のマスに戻る
これで解けます。
$9^{81}$通りくらい試すことになりそうですが、いい感じに枝刈りされてすぐに答えが出ます。
Demo
アルゴリズムの動作のイメージはこんな感じです。
https://ia7ck.github.io/visualization/backtracking/sudoku/index.html
ソースコード
データは 1 million Sudoku games | Kaggle のものを使いました。
