Irakli Koiava

Heap Sort         დალაგება გროვებით როგორც სათაურიდანაც კარგად ჩანს დაფუძნებულია გროვებზე . გროვებით სორტირების პრინციპი შემდეგია: პირველ რიგში ჩვენ ვაგებთ გროვას, რასაც ჭირდება O(n) დრო. შემდეგ ვაგდებთ მაქსიმუმს(გროვის ძირს) გროვიდან, გადაგვაქვს დალაგებული მასივის თავში(ამას ჭირდება O(log()) დრო) და ამ პროცესს ვიმეორებთ მანამ, სანამ გრობვა არ დაცარიელდება. პრაქტიკულად გროვის დალაგება ხდება იგივე მასივის ბოლოში რომელშიც მოწესრიგებულია თავად გროვა. დროის ეს შეფასება არის ბევრად უფრო სტაბილური ვიდრე ჩქარი დალაგებისას სადაც უარეს შემთხვევაში დრო O(n^2)-მდეც კი ადის, რაც გროვებში არასდროს ხდება. თუმცა შემთხვევითი რიცხვებისათვის ის უფრო ნელია ჩქარ დალაგებასთან შედარებით. ქვემოთ მოცემულ სურათზე ნაჩვენებია გროვებით დალაგების ალგორითმის მუშაობის პროცესი ანიმაციურად.         მოვიყვანოთ ალგორითმის განხორციელების კონკრეტული მაგალითი. პროგრამული კოდი დაწერილია C -ზე: void  Heapify (  int  k ,  int  a [],  i...

Binary Heap         გროვა არის მონაცემთა სტრუქტურა რომელშიც მონაცემები ისე არიან მოწესრიგებული რომ მონაცემების ექსტრემუმებზე წვდომა გვაქვს განსაკუთრებით ადვილად. არსებობს მაქსიმუმისა და მინიმუმის გროვები, მაქსიმუმის გროვაში ჩვენ მაქსიმალური მნიშვნელობის ელემენტს შეგვიძლია მინწვდეთ ერთ ოპერაციაში, ხოლო მინიმუმის გროვაში მინიმუმს. ამოცანის სპეციფიკიდან გამომდინარე უნდა გამოვიყენოთ შესაბამისი ტიპის გროვა. მაქსიმუმისა და მინიმუმის გროვის მუშაობის პრინციპი არის ერთი ამიტომ მაგალითისათვის ჩვენ განვიხილოთ მინიმუმის გროვა. ახლა რაც შეეხება თვითონ მის სტრუქტურას.   გროვა არის ორობითი ხე, თუმცა უბრალო ორობითი ხისაგან ის განსხვავდება შემდეგი თვისებით: გროვის ნებისმიერ კვანძში შვილობილი კვანძის  მნიშვნელობა არ უნდა აღემატებოდეს მშობელი კვანძისას. ამ თვისებას გროვის ძირითად თვისებას უწოდებენ. გროვის ხე არ უნდა იყოს არათანაბრად გაზრდილი. ხე უნდა იზრდებოდეს სიმაღლეში თანაბრად. რაც გვაძლევს იმის საშუალებას რომ გროვა განვათავსოთ მასივში. ამ შემთხვევაში მე...