8.4 まとめ¶
1. 重要なポイントの振り返り¶
- ヒープは完全二分木であり、条件の違いによって最大ヒープと最小ヒープに分けられる。最大（最小）ヒープの根の要素は最大値（最小値）である。
- 優先度付きキューとは、取り出し時に優先度が考慮されるキューであり、通常はヒープを用いて実装される。
- ヒープの代表的な操作とそれに対応する時間計算量には、要素の挿入 \(O(\log n)\)、根の要素の削除 \(O(\log n)\)、根の要素へのアクセス \(O(1)\) などがある。
- 完全二分木は配列で表現するのに非常に適しているため、通常は配列を使ってヒープを格納する。
- ヒープ化操作はヒープの性質を保つために用いられ、挿入操作と削除操作の両方で使用される。
- \(n\) 個の要素を入力してヒープを構築する時間計算量は \(O(n)\) まで最適化でき、非常に効率的である。
- Top-k は古典的なアルゴリズム問題であり、ヒープ構造を用いることで効率的に解くことができ、時間計算量は \(O(n \log k)\) である。
2. Q & A¶
Q：データ構造の「ヒープ」とメモリ管理の「ヒープ」は同じ概念ですか？
両者は同じ概念ではなく、たまたまどちらも「ヒープ」と呼ばれているだけである。コンピュータシステムのメモリにおけるヒープは動的メモリ割り当ての一部であり、プログラムは実行時にこれを使ってデータを格納できる。プログラムは一定量のヒープメモリを要求し、オブジェクトや配列などの複雑な構造を保存できる。これらのデータが不要になったときは、メモリリークを防ぐためにそのメモリを解放する必要がある。スタックメモリと比べると、ヒープメモリの管理と使用にはより慎重さが求められ、不適切に扱うとメモリリークやダングリングポインタなどの問題を引き起こす可能性がある。