So the last thing I promised I would tell you about
is inserting elements into a heap.
And that turns out not to be all that hard,
but it does involve some coding that we haven't done yet.
The idea is that the new element that we're going to insert
we stick at the sort of bottom right corner of the heap.
Or, if the heap was already full, then the far left.
But now we have potentially violated the heap property,
so this node to it's parent could be problematic.
So, essentially, we need to do
some sort of an analog of down-heapify that I call up-heapify
that takes this value that might be problematic,
swaps it up if it is,
and then continues to swap it up the tree
until it reaches a place where it is smaller than both of its children.
At which point, the heap property is satisfied globally.
So I'm going to leave that as a homework problem for you
to actually code up-heapify,
and that gives us the insert that we need.
So now that we can insert and delete into heaps and (logn) time,
we can use this to solve the TopK problem
that we've been talking about throughout this unit.
By running through the list of the N elements that we want the TopK of,
and meanwhile we keep a heap of size K off to the side,
and so we're trying to the largest K, in this case.
So each new element that we encounter
we ask, is this element bigger than the smallest
value that we've kept so far?
So does it deserve to be in the TopK so far?
If not, we can just throw it away,
because we know it's not going to be part of the TopK.
If it is, then the smallest thing in that heap
no longer needs to be there, because we found something better.
So we delete min,
and we insert the new value that we just got into the heap
and reestablish the heap property
by--well, we could do it as a down-heapify, actually,
because we deleted the node from the top.
We can replace it with something else.
So, for each of N times,
we do possibly one insert into the heap,
which is a log K operation.
So the total running time ends up being we do (nlogk) operations.
So that's actually pretty efficient.
It doesn't solve the TopK problem better
than the randomized algorithm we talked about--
the partitioning algorithm--
but it does it pretty fast
and there's other uses for this.
We'll see that in the next unit.
Thanks a lot, and good luck with the homework.
तो आखिरी बात मैं वादा किया था मैं आप के बारे में बताना होगा
तत्व एक ढेर में सम्मिलित है।
और जो चला है कि सभी मुश्किल, नहीं किया जा करने के लिए बाहर
लेकिन यह कुछ कोडन कि हम अभी तक नहीं किया है को शामिल करता है।
विचार है कि नए तत्व है कि हम को सम्मिलित करने के लिए जा रहे हैं
हम ढेर के नीचे दायें कोने की तरह है पर छड़ी।
या, यदि ढेर पहले से ही भरा, था तब तक बाईं।
लेकिन अब हम संभावित ढेर संपत्ति का उल्लंघन किया है,
तो यह माता पिता के लिए इस नोड समस्याग्रस्त किया जा सकता है।
तो, मूलतः, हमें करना चाहिए
कुछ प्रकार के एक एनालॉग के डाउन-heapify मैं कहते हैं कि अप-heapify
कि समस्याग्रस्त किया जा सकता है यह मान लेता है,
यदि यह है यह ऊपर स्वैप,
और तब यह पेड़ को स्वैप करने के लिए जारी है
जब तक यह एक जगह है जहाँ यह दोनों को अपने बच्चों से भी छोटा होता है तक पहुँच।
जो बिंदु पर, ढेर संपत्ति विश्व स्तर पर संतुष्ट है।
तो मैं कि आप के लिए एक होमवर्क समस्या के रूप में छोड़ने के लिए जा रहा हूँ
वास्तव में कोड करने के लिए अप-heapify,
और जो हमें डालें कि हम की जरूरत है देता है।
तो अब है कि हम सम्मिलित करें और ढेर में नष्ट कर सकते हैं और (logn) समय,
हम इस TopK समस्या को हल करने के लिए उपयोग कर सकते हैं
हम के बारे में इस इकाई में किया गया है कि बात कर रही।
N तत्वों है कि हम का TopK चाहते हैं की सूची के माध्यम से चल रहे हैं,
और इस बीच हम पक्ष के लिए एक ढेर आकार कश्मीर बंद के रख,
और इसलिए हम इस मामले में सबसे बड़ा K करने के लिए, कोशिश कर रहे हैं।
तो एक नया तत्व है कि हम मुठभेड़
हम चाहते हैं, इस तत्व से सबसे छोटा बड़ा है
मूल्य है कि हम अभी तक रखा है?
तो यह TopK में अब तक के लायक है?
यदि नहीं, तो हम बस इसे दूर फेंक कर सकते हैं,
क्योंकि हम जानते हैं कि यह TopK का हिस्सा बनने के लिए नहीं जा रहा है।
अगर ऐसा है, तो उस ढेर में छोटी से छोटी बात
क्योंकि हम कुछ बेहतर पाया अब वहाँ, हो की जरूरत है।
तो हम न्यूनतम हटाने,
और हम हम सिर्फ ढेर में मिला नया मान सम्मिलित करें
और ढेर संपत्ति पुनर्स्थापित करना
द्वारा - ठीक है, हम के रूप में यह कर सकता है एक डाउन-heapify, वास्तव में,
क्योंकि हम नोड ऊपर से हटा दिया।
हम इसे कुछ और के साथ प्रतिस्थापित कर सकते हैं।
तो, प्रत्येक N बार के लिए,
हम ढेर में संभवतः एक सम्मिलित करते हैं,
जो एक लॉग K ऑपरेशन है।
तो के लिए कुल समय चलाने समाप्त होने के नाते हम (nlogk) संचालन करते हैं होता है।
तो है कि वास्तव में बहुत कुशल है।
यह बेहतर TopK समस्या का समाधान नहीं करता
यादृच्छिक एल्गोरिथ्म से भी हम के बारे में बात की-
विभाजन कलन विधि-
लेकिन यह बहुत तेजी से करता है
और वहाँ इस के लिए अन्य का उपयोग करता है।
हम कि अगले यूनिट में देखता हूँ।
धन्यवाद एक बहुत, और होमवर्क के साथ अच्छे भाग्य।
最後に説明するのはヒープへの要素の挿入です
さほど難解ではありませんが まだ学習していないコードが出てきます
考え方としては新しい要素を挿入する場所を
ヒープの底の右端とすることです
ヒープの底がすでに埋まっていたら一番左に置きます
ヒープのプロパティを壊す可能性があります
このノードと親の関係に問題があるかもしれません
そこで問題がある可能性を持つこの値に
down_heapifyとは逆のup_heapifyを行います
2個の子ノードの値よりも 小さくなる場所にたどり着くまで
この値と上位のノードとの置き換えを続け
たどり着いたら全体がヒープとなります
では宿題です up_heapifyのコードを書いてください
挿入アルゴリズムが必要になります
要素をヒープに挿入し削除することができます 時間はnの対数です
これを使いこのレッスンで話してきた Top-k問題を解決できます
Top-kを見つけたいn個の要素を含むリストを実行します
一方kの大きさのヒープは横に置いておきます
この場合は最大値のkを探します
新しい要素に遭遇するたびに
これは今までで一番小さい値よりも大きいか尋ねます
Top-kに入れるかということです
大きくなければTop-kに入らないので捨てます
大きい場合この時点で一番小さい値は
もっとふさわしい値が見つかったので除きます
そしてこの新しい値をヒープに挿入します
ヒープのプロパティが再確立できました
down_heapifyを使うこともできます
ノードを一番上から除き他と置き換えるからです
それぞれn回ずつ
ヒープに値を挿入します これはkの対数のオペレーションです
したがって全体の実行時間は Θ(n log k)になります
これはかなり効率的です
Top-k問題を解決するには
乱択化アルゴリズムや分割アルゴリズムを 使う方がいいのですが
この方法もかなり速く他にも用途があります
それは次のレッスンで見ていきます
では宿題を頑張ってください