0

要素をヒープに挿入するには、その要素を配列の最後に追加し、それが「適切な場所」にあり、ヒーププロパティ（その操作はO（logn））を満たすまで上向きに伝搬する必要があります。

ただし、たとえばCではrealloc、新しい要素の配列のサイズを変更するために呼び出すと、配列全体をメモリ内の別の場所（最適な場合はO（n））にコピーする必要が生じる可能性があります（おそらくそうなります）。最悪の場合ですよね？

C（またはそれに関しては任意の言語）のヒープは通常、固定された事前に割り当てられたサイズで実行されますか、または動的にサイズ設定されたヒープを実行可能な選択にするのに十分なほど重要ではないコピー操作です（たとえば、迅速に維持するためのバイナリヒープ）アイテムの検索可能なリスト）？

4

1 に答える 1

2

典型的なスキームは、部屋がなくなったときにサイズを 2 倍にすることです。この倍増とそれに伴うコピーには、実際に O(n) 時間がかかります。

ただし、この倍加を頻繁に実行する必要はないことに注意してください。倍増を伴わないヒープで実行されたすべての操作の倍増の総コストを平均すると、コストは実際には取るに足らないものになります。(この種の平均化は、償却分析として知られています。)

于 2012-06-05T13:50:51.643 に答える