Japanese subtitles

← 04-50 Inserting Elements

Get Embed Code
3 Languages

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

  1. 最後に説明するのはヒープへの要素の挿入です
  2. さほど難解ではありませんが
    まだ学習していないコードが出てきます
  3. 考え方としては新しい要素を挿入する場所を
  4. ヒープの底の右端とすることです
  5. ヒープの底がすでに埋まっていたら一番左に置きます
  6. ヒープのプロパティを壊す可能性があります
  7. このノードと親の関係に問題があるかもしれません
  8. そこで問題がある可能性を持つこの値に
  9. down_heapifyとは逆のup_heapifyを行います
  10. 2個の子ノードの値よりも
    小さくなる場所にたどり着くまで
  11. この値と上位のノードとの置き換えを続け
  12. たどり着いたら全体がヒープとなります
  13. では宿題です up_heapifyのコードを書いてください
  14. 挿入アルゴリズムが必要になります
  15. 要素をヒープに挿入し削除することができます
    時間はnの対数です
  16. これを使いこのレッスンで話してきた
    Top-k問題を解決できます
  17. Top-kを見つけたいn個の要素を含むリストを実行します
  18. 一方kの大きさのヒープは横に置いておきます
  19. この場合は最大値のkを探します
  20. 新しい要素に遭遇するたびに
  21. これは今までで一番小さい値よりも大きいか尋ねます
  22. Top-kに入れるかということです
  23. 大きくなければTop-kに入らないので捨てます
  24. 大きい場合この時点で一番小さい値は
  25. もっとふさわしい値が見つかったので除きます
  26. そしてこの新しい値をヒープに挿入します
  27. ヒープのプロパティが再確立できました
  28. down_heapifyを使うこともできます
  29. ノードを一番上から除き他と置き換えるからです
  30. それぞれn回ずつ
  31. ヒープに値を挿入します
    これはkの対数のオペレーションです
  32. したがって全体の実行時間は
    Θ(n log k)になります
  33. これはかなり効率的です
  34. Top-k問題を解決するには
  35. 乱択化アルゴリズムや分割アルゴリズムを
    使う方がいいのですが
  36. この方法もかなり速く他にも用途があります
  37. それは次のレッスンで見ていきます
  38. では宿題を頑張ってください