Hindi subtitles

← 04-50 Inserting Elements

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. तो आखिरी बात मैं वादा किया था मैं आप के बारे में बताना होगा
  2. तत्व एक ढेर में सम्मिलित है।
  3. और जो चला है कि सभी मुश्किल, नहीं किया जा करने के लिए बाहर
  4. लेकिन यह कुछ कोडन कि हम अभी तक नहीं किया है को शामिल करता है।
  5. विचार है कि नए तत्व है कि हम को सम्मिलित करने के लिए जा रहे हैं
  6. हम ढेर के नीचे दायें कोने की तरह है पर छड़ी।
  7. या, यदि ढेर पहले से ही भरा, था तब तक बाईं।
  8. लेकिन अब हम संभावित ढेर संपत्ति का उल्लंघन किया है,
  9. तो यह माता पिता के लिए इस नोड समस्याग्रस्त किया जा सकता है।
  10. तो, मूलतः, हमें करना चाहिए
  11. कुछ प्रकार के एक एनालॉग के डाउन-heapify मैं कहते हैं कि अप-heapify
  12. कि समस्याग्रस्त किया जा सकता है यह मान लेता है,
  13. यदि यह है यह ऊपर स्वैप,
  14. और तब यह पेड़ को स्वैप करने के लिए जारी है
  15. जब तक यह एक जगह है जहाँ यह दोनों को अपने बच्चों से भी छोटा होता है तक पहुँच।
  16. जो बिंदु पर, ढेर संपत्ति विश्व स्तर पर संतुष्ट है।
  17. तो मैं कि आप के लिए एक होमवर्क समस्या के रूप में छोड़ने के लिए जा रहा हूँ
  18. वास्तव में कोड करने के लिए अप-heapify,
  19. और जो हमें डालें कि हम की जरूरत है देता है।
  20. तो अब है कि हम सम्मिलित करें और ढेर में नष्ट कर सकते हैं और (logn) समय,
  21. हम इस TopK समस्या को हल करने के लिए उपयोग कर सकते हैं
  22. हम के बारे में इस इकाई में किया गया है कि बात कर रही।
  23. N तत्वों है कि हम का TopK चाहते हैं की सूची के माध्यम से चल रहे हैं,
  24. और इस बीच हम पक्ष के लिए एक ढेर आकार कश्मीर बंद के रख,
  25. और इसलिए हम इस मामले में सबसे बड़ा K करने के लिए, कोशिश कर रहे हैं।
  26. तो एक नया तत्व है कि हम मुठभेड़
  27. हम चाहते हैं, इस तत्व से सबसे छोटा बड़ा है
  28. मूल्य है कि हम अभी तक रखा है?
  29. तो यह TopK में अब तक के लायक है?
  30. यदि नहीं, तो हम बस इसे दूर फेंक कर सकते हैं,
  31. क्योंकि हम जानते हैं कि यह TopK का हिस्सा बनने के लिए नहीं जा रहा है।
  32. अगर ऐसा है, तो उस ढेर में छोटी से छोटी बात
  33. क्योंकि हम कुछ बेहतर पाया अब वहाँ, हो की जरूरत है।
  34. तो हम न्यूनतम हटाने,
  35. और हम हम सिर्फ ढेर में मिला नया मान सम्मिलित करें
  36. और ढेर संपत्ति पुनर्स्थापित करना
  37. द्वारा - ठीक है, हम के रूप में यह कर सकता है एक डाउन-heapify, वास्तव में,
  38. क्योंकि हम नोड ऊपर से हटा दिया।
  39. हम इसे कुछ और के साथ प्रतिस्थापित कर सकते हैं।
  40. तो, प्रत्येक N बार के लिए,
  41. हम ढेर में संभवतः एक सम्मिलित करते हैं,
  42. जो एक लॉग K ऑपरेशन है।
  43. तो के लिए कुल समय चलाने समाप्त होने के नाते हम (nlogk) संचालन करते हैं होता है।
  44. तो है कि वास्तव में बहुत कुशल है।
  45. यह बेहतर TopK समस्या का समाधान नहीं करता
  46. यादृच्छिक एल्गोरिथ्म से भी हम के बारे में बात की-
  47. विभाजन कलन विधि-
  48. लेकिन यह बहुत तेजी से करता है
  49. और वहाँ इस के लिए अन्य का उपयोग करता है।
  50. हम कि अगले यूनिट में देखता हूँ।
  51. धन्यवाद एक बहुत, और होमवर्क के साथ अच्छे भाग्य।