8.4   まとめ

1.   重要な復習

• ヒープは完備二分木で、その構築性質に基づいて最大ヒープまたは最小ヒープに分類できます。最大ヒープの先頭要素は最大で、最小ヒープの先頭要素は最小です。
• 優先度キューは、デキューの優先度を持つキューとして定義され、通常ヒープを使用して実装されます。
• ヒープの一般的な操作とそれに対応する時間計算量には以下があります：ヒープへの要素挿入\(O(\log n)\)、ヒープからの先頭要素削除\(O(\log n)\)、ヒープの先頭要素へのアクセス\(O(1)\)。
• 完備二分木は配列で表現するのに適しているため、ヒープは一般的に配列を使用して格納されます。
• ヒープ化操作はヒープの性質を維持するために使用され、ヒープの挿入操作と削除操作の両方で使用されます。
• \(n\)個の要素が入力として与えられた場合のヒープ構築の時間計算量は\(O(n)\)に最適化でき、これは非常に効率的です。
• Top-kは古典的なアルゴリズム問題で、ヒープデータ構造を使用して効率的に解決でき、時間計算量は\(O(n \log k)\)です。

2.   Q & A

Q: データ構造の「ヒープ」とメモリ管理の「ヒープ」は同じ概念ですか？

この2つは、どちらも「ヒープ」と呼ばれますが、同じ概念ではありません。コンピュータシステムメモリのヒープは動的メモリ割り当ての一部で、プログラムが実行中にデータを格納するために使用できます。プログラムは、オブジェクトや配列などの複雑な構造を格納するために、一定量のヒープメモリを要求できます。割り当てられたデータが不要になったときは、メモリリークを防ぐためにプログラムがこのメモリを解放する必要があります。スタックメモリと比較して、ヒープメモリの管理と使用にはより多くの注意が必要で、不適切な使用はメモリリークやダングリングポインタにつながる可能性があります。