Japanese subtitles

← 04-45 Remove Min

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ヒープをベースにした技術を使う利点は
  2. 2つの操作が効率的に行える点です
  3. 最小値を見つけて取り除くことと
    新しい要素の挿入です
  4. この2つの操作をnの対数で実行したらこれを
  5. 先ほど説明したTop-kのシナリオに当てはめます
  6. 最小値を見つけるのは簡単です 一番上のここです
  7. 最小値を求めるのは簡単で定数時間です
  8. 問題は最小値を除く場合です
  9. 山頂がくぼんだ火山みたいに見えますが
    これを修正していきます
  10. 大きなヒープを小さな2つのヒープに分けます
  11. でも本当に欲しいのは1つのヒープです
  12. このあたりにノードを置けばそこから
  13. down_heapifyを実行できます
  14. でも自然なノードの位置はヒープの最後です
  15. ヒープから離れても全体の構造を傷つけません
  16. これをトップに動かしdown_heapifyを実行します
  17. これがnの対数時間で完結しヒープができます
  18. ステップはまず
  19. Lのノード0を削除し
    最後のノードを一番上にコピーします
  20. 少し小さくなったヒープをdown_heapifyします
  21. 要素の数はn-1です
    down_heapifyを実行します
  22. Θ(log n)でヒーププロパティが再確立しました
  23. Pythonコードを書いてください
    数行で済むはずです
  24. down_heapifyとbuild_heapアルゴリズムを使って
  25. リストからヒープを作り最小値を除いてください