სტრუკტურული მონაცემები - (ხე, Heap)

 

                                                                Heap

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

1.     მაქსიმალური ღირებულებით (Max Heap)

2.     მინიმალური ღირებულებით. (Min Heap)

მისი ყველაზე ცნობილი იმპლემენტაცია გახლავთ პრიორიტეტული რიგი (PriorityQueue) java.util.Queue პაკეტიდან. თუ გახსოვთ PriorityQueue-ში როგორ ხდება ელემენტების განლაგება, ხის აღქმა არ გაგიჭირდებათ, ვისაც არ გახსოვთ მაგათვის: Heap-ში ელემენტები განლაგებულია პრიორიტეტების მიხედვით პრიორიტეტული ელემენტი არის Root კვანძი, ის შეიძლება იყოს მაქსიმალური ღირებულების მატარებელი ხეში, ან მინიმალური ღირებულების. სხვა ყველა ოპერაცია ამ პრიორიტეტის ირგვლივ არის აგებული, შესაბამისად ხის აგებისთვის ვიცავთ 2 წეს, იმის გათვალისწინებით თუ რომელ ხეს ვაგებთ(Max/Min)

1.     მშობელი კვანძი მეტი უნდა იყოს შვილობილ კვანძ-ზე (parent > child)

2.     მშობელი კვანძი ნაკლები უნდა იყოს შვილობილ კვანძ-ზე (parent < child)

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

                                              

ამ ეტაპისთვის არ გვაქ დრღვევა, გავაგრძელოთ:

             

         

5 მეტია მის მშობელ 4-ზე, ხე არის დარღვევებით, ასეთ სიტუაციაში, ადგილს ვუცვლით დამრღვევ კვანძს და მის მშობელ კვანძს.

                                   

ადგილის ცვლას კი გავნაგრძნობთ მანამ სანამ არ მივალთ Root კვანძამდე. შემდეგი ელემენტია 12 და ის განთავსდება კვანძი ნომერი 5-ის ხელ-მარჯვნივ, ვინაიდან 12 მეტია 5-ზე ისინი ადგილებს შეიცვლიან, 12 მეტია 10-ზეც და Root კვანძი გახდება 12:

                          

ყველა დანარჩენი ელემენტის დამატება დაიცავს იგივე წეს.

ყველაზე ხშირად ამ ხის აგება ხდება მასივზე დაყრდნობით, რაც აგების პროცეს გაცილებით მარტივს ხდის. თუ წარმოვიდგენთ შემდეგ ხეს:

მასივში ელემენტების განლაგება მოხდება შემდეგი თანმიმდევრობით.

Root ელემენტი ყოველთვის იქნება Array[0], ყველა სხვა დანარჩენი ელემენტი კი თანმიმდევრობით მოყვება მას. 5, 9, 11, 14, 18, 19, 21, 33, 17, 27. ამ ყველაფრის შემდგომ ალბათ ჩნდება ლოგიკური კითხვა, Heap თუ ხეა და მისი აგება ხდება მასივზე დაყრდნობით, როგორ ხდება მასივში მშობელი კვანძის, მარცხენა და მარჯვენა კვანძების გამორჩევა? როგორ უნდა მივხვდეთ რო 27-ის მშობელი არის 18? ამის გაგებაში ერთი ფორმულა დაგვეხმარება. ყველა ახალი დამატებული ელემენტის მშობელი არის ბოლო ინდექს -1 გაყოფილი ორზე. დაუშვათ დავამატეთ ფოტოზე ელემენტი ნომერი 9, რომელიც იმყოფება Array[1],  ფორმულას ექნება შემდეგი სახე. (lastElement-1)/2. ან (size-1)/2 თუ ელემენტი ნომერი 9-ის ინდექს ჩავსვამთ ფორმულაში, მივიღებთ (1-1)/2 რაც უდრის 0-ს. ელემენტი ინდექს 0-ზე არის მშობელი ელემენტი ნომერი 9-ის. იგივე ფორმულით მიუდგებით ყველა სხვა ელემენტსაც. ელემენტი ნომერი 27 იმყოფება ინდექს ნომერ 9-ზე. (9-1)/2 უდრის 4. მშობელი ელემენტი 27-ის იმყოფება მეოთხე ინდექსზე. ამის შემდგომ თუ ელემენტი ინდექს 9-ზე მეტია ელემენტ ინდექს 4-ზე შეუცვალეთ მათ ადგილები. ადგილის შეცვლა როგორ ხდება ეგეც იცით. მაგალითისთვის: E number = array[parent]; array[parent] = array[lastElement]; array[lastElement] = number; გაიმეორებთ ამ ოპერაციას მანამ სანამ არ მიხვალთ Root კვანძამდე, რეკურსიულად ან  იტერაციულად. მშობელის მოძიება გჭირდებათ მხოლოდ დამატების დროს, წაშლის დროს კი დაგჭირდებათ მარცხენა და მარჯვენა შვილობილი კვანზების მონახვა. მათ-ზე ცოტა ხანში ვისაუბრებთ. ახლა კი ნახეთ დამატების მეთოდი.

პირველ გამოხატულებაში ვაკონტროლებთ, რომ ხეს ცარიელი ელემენტი არ გადაეცეს. შემდგომ გამოხატულებაში ვაკონტროლებთ ხის სიდიდეს, თუ ის შეივსება მაშინ ადგილის გაზრდა მოგვიწევს, როგორც ArrayList ან ნებისმიერ სხვა მასივზე ბაზირებულ სტრუკტურაში:

ამ კონრეტულ შემთხვევაში ხეს ვზრდი არსებულ სიდიდეს +1 + თუ ძველი სიდიდე ნაკლებია 100, მაშინ ძველ სიდიდეს +2-ით ან ძველი სიდიდის ნახევარით. მე ვზრდი ესე თორე არ არის აუცილებელი თქვენც ესე გაზარდოთ, თქვენი გემოვნების და მოთხოვნის მიხედვით დაწერთ ამ მეთოდს. როგორც ესეთი მაგალითისთვის არის შექმნილი, რეალურ პროგრამირებაში უამრავი დეტალის გათვალისწინება მოგიწევთ, მაგალითად მეხსიერების გადავსების დროს როგორ უნდა იმოქმედოს გაზრდის მეთოდმა, თუ მეხეირებაში ადგილია დარჩენილი როგორი ოპტიმალური სიდიდთ გაიზარდოს და ა.შ. მესამე გამოხატულებაში ვამოწმებთ მასივი ცარიელია თუ არა, თუ ცარიელია მაშინ პირველი ელემენტი, elements[0] უდრის დამატებულ ელემენტს, წინააღმდეგ შემთხვევაში, მასივში უკვე არის ელემენტები, გავზრდით ბოლო ელემენტის ინდექს და გადავაწოდებთ ელემენტს მეთოდს, რომელიც გადაგვიმოწმებს ხომ არ არღვევს ის ხის წესებს.

თუ გადაწოდებული ელემენტი უდრის 0-ს მაშინ მეთოდი უნდა გავიდეს მეხსიერებიდან, ისე Add მეთოდიდან გადაწოდებული ელემენტი არასდროს იქნება 0, მაგრამ მეთოდი რეკურსიულია და როგორც გახსოვთ, რეკურსიის ერთადერთი და მთავარი წესი არის მოვახდინოთ დეფინირება მეხსიერებიდან გასვლის წერტილის. ამ შემთხვევაში lastElement == 0-ან დატოვებს მეთოდი მეხსიერებას. შემდეგ ველზე ვპოულობთ გადაწოდებული ელემენტის მშობელ კვანძს (უფრო სწორად მის იდექს მეხსიერებაში) და ამის შემდგომ ვიწყებთ ოპერაციის წარმოებას, როგორც ხედავთ, მეთოდი მუშაობს როგორც Comparator ის Comparable-ით, Default შედარების სისტემად Comparable მაქ არჩეული, რომელიც ელემენტებს მეხსიერებაში აღმავლობის პრინციპით განალაგებას, ანუ ეს კონრეტული ხე არის Max Heap, მაგრამ მომხმარებელს არასდროს ექნება იმის შეზღუდვეა რო ელემენტების პრიორიტეტი აირჩიოს თვითონ, რაშიც Comparator დაეხმარება, მოუძებნის ბოლო ელემენტს მეხსიერებაში, მოუძებნის მის მშობელს, შემდგომ შევადარებთ ბოლო ელემენტს და მშობელს ერთმანეთს, თუ ბოლო ელემენტი დიდია მშობელ ელემენტზე ელემენტებს შეუცვლით ადგილს.  იგივე ოპერაციას ასრულებს Comparable, else ბლოკში. მეთოდის ბოლოს კი რეკურსიულად ვაწოდებთ მშობელ ელემენტს მეთოდს. არც ისე რთულად გამოიყურება დამეთანხმებით, მე თუ მკითხავთ ამ ხეს ხესაც ვერ ვუწოდებთ, ჭკვიანი მასივია, მაგრამ ვინაიდან მთელი მსოფლიო ხეს ეძახის, ჩვენც მივყვეთ დინებას.

ვნახეთ როგორც ხდება Heap-ზე ელემენტის დამატება, როგორ ხდება მისი სორტირება, დროა ვნახოთ როგორ ხდება ხიდან ელემენტის წაშლა. თუმცა სანამ მეთოდს ვნახავდეთ მანამდე წესებს გავეცნოთ.

1.     Heap-ან იშლება მხოლოდ Root ელემენტი, array[0].

2.  Root ელემენტი, რომ წავშალოთ მას უნდა მოუნახოთ იდეალური შემცვლელი, ამ კონკრეტულ ხეში, იდეალური შემცვლელი არის ბოლო დამატებული ელემენტი.

3.  იდეალური შემცვლელის მონახვის შემდგომ მას ვაქცევთ Root კვანძად და ვიწყებთ ელემენტების ცვლას მაღლიდან დაბლა. ელემენტი მაღლიდან დაბლა ეფეკტურად რომ ვცვალოთ უნდა მოუნახოთ მარჯვენა და მარცხენა შვილობილი კვანძები.

4.     მარცხენა შვილობილი კვანძის ფორმულა: 2 * parent + 1;

5.     მარჯვენა შვილობილი კვანძის ფორმულა : 2 * parent +2;

მეთოდი, რომელიც შლის კვანძს ხიდან:

თუ გაგიკვირდათ და იფიქრეთ, ეს 6 ველი როგორ ასრულებს ამდენ ოპერაციასო, დამიჯერეთ, ასრულებს! ალბათ მთლიან აბსტრაკტულ სტრუკტურაში, ყველაზე პატარა წაშლის მეთოდია, როგორც წესი მიჩვეული ვართ რო ელემენტის სტრუკტურიდან მოშორება ყველაზე ფაქიზი, ტევადი და რთული ოპერაციაა. განვიხილოთ რა ხდება მეთოდში.  პირველი რასაც ვაკეთებთ, ვინახავთ ელემენტს რომელსაც ვშლით, მოგვიანებით რო დაუბრუნოთ მომხმარებელს.  შემდეგ ველზე პირველ Root ელემენტს და ბოლო ელემენტს უცვლით მეხსიერებაში ადგილს:

ამის შემდგომ ახალ Root ელემენტს ვწევთ დაბლა, სხვა ენით ხეში ყველაზე დიდ ელემენტს ვწევთ მაღლა. დაუშვათ თუ root=50 და ბოლო ელემენტი = 10. ადგილის შეცვლის შემდგომ root=10 რაც დარღვვევაა წესების MaxHeap-ში, ელემენტის დაბლა ჩაწევაში დაგვეხმარება ფორმულები, რომლებიც მოგვინახავს მარცხენა და მარჯვენა შვილობილ კვანძებს,  მონახვის შემდგომ პირველი რასაც გავაკეთებთ ეს არის , რომ მარცხენა კვანძს შევადარებთ მარჯვენა კვანძს, თუ მარცხენა დიდია, root კვანძი გაუცვლის ადგილს მარცხენა კვანძს, წინააღმდეგ შემთხვევაში მარჯვენა კვანძს, ეს ოპერაცია გაგრძელდება მანამ სანამ ელემენტი ნომერი 10 არ მონახავს მასივში მისთვის იდეალურ პოზიციას, პოზიციას სადაც მისი ორივე შვილობილი კვანძი მასზე პატარა იქნება. ნახეთ ოპერაცია:

ფოტოზე მხოლოდ comparator-ის მაგალითი დაეტია, Comparable მაგალითს ნახავთ Github-ზე. როგორც ხედავთ ოპერაციას ვიწყებთ შვილობილი კვანძების მოძებნით. მოძებნის შემდგომ, ვპოულობთ არსებულ ინდექსებზე ობიეკტებს, ობიეკტების მოძიების შემდგომ პირველ გამოხატულებაში, ვამოწმებთ ხეში ხომ არ არის 2 ელემენტი, თუ მხოლოდ 2 ელემენტია და ეს ელემენტები არიან root და მარცხენა კვანძი, მაშინ შეუცვლით მათ ადგილებს და დავტოვებთ მეხსიერებას, იგივეს გავაკეტებთ შემდგომ გამოხატულებაში მარჯვენა კვანძტთან მიმართებაში და ა.შ. მთლიანი ფოტო ვერ ჩაჯდა ჩარჩოებში სამწუხაროდ.

ალბათ გახსოვთ, რომ პრიორიტეტულ რიგს გააჩნია ნებისმიერი ელემენტის წაშლის უნარიც, მიუხედავად იმისა რო Heap-ში იშლება მხოლოდ Root ელემენტი, ჯავას დეველოპერები შლიან ნებისმიერ ელემენტსაც, საინტერესოა როგორ აკეთებენ ამას? ლოგიკა იგივეა, უბრალოდ ადგილს უცვლით წასაშლელ ელემენეტს და ბოლო ელემენტს, ამის შემდგომ თუ ახალი ელემენტი, რომელმაც წაშლილი ელემენეტის ადგილი დაიკავია მეტია მშობელ-ზე(თუ MaxHeap-ს ვაკეთებთ) მაშინ ელემენტს ავწევთ მაღლა, თუ ნაკლებია შვილობილ კვანძებზე მაშინ დავწევთ დაბლა. ამით Heap-ზე საუბარს მოვრჩით. თუ რამე გაუგებარი იყო ან კოდში მიაგენით ლოგიკურ ბაგებს მომწერეთ პირადში. სრული კოდის სანახავად გადადით შემდეგ ბმულზე.