ორობითი გროვა და პრიორიტეტული რიგი

სასწრაფო დახმარების განყოფილება, პროცესორის დამგეგმავი, დეიქსტრას ალგორითმი: ყველა მათგანი გამუდმებით კითხულობს, „რომელია ახლა ყველაზე სასწრაფო?“. ორობითი გროვა O(1)-ში პასუხობს და O(log n)-ში ახლდება, ჩვეულებრივ მასივში.

★ ლექცია: tree_heap · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 12 წთ

←ეყრდნობა

5ხეები: ცნებები, თვისებები, შემოვლებიგროვა სრული ორობითი ხეა, სადაც ყოველი მშობელი თავის შვილებზე პატარაა.1მასივები და დინამიური მასივებიგროვა მასივში ცხოვრობს: i-ს შვილები 2i+1 და 2i+2 ადგილებზე არიან.3რიგი (FIFO) და დეკიპრიორიტეტული რიგი ისეთი რიგია, სადაც პირველი უმცირესი გამოდის და არა უძველესი.

გზას უხსნის→

8დეიქსტრას ალგორითმიდეიქსტრა კანდიდატ მანძილებს მინ-გროვაში ინახავს.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01რა სჭირდება პრიორიტეტულ რიგს

პრიორიტეტული რიგი ინახავს ელემენტებს პრიორიტეტებით და სამ ოპერაციას უჭერს მხარს: ელემენტის ჩასმა, უმცირესის (ან უდიდესის) ნახვა და მისი ამოღება. ცხადი სტრუქტურები სადღაც ცდება:

დალაგებული მასივი: ნახვა იაფია, მაგრამ ჩასმისას ელემენტები უნდა გადავწიოთ, O(n);
დაულაგებელი მასივი: ჩასმა O(1)-ია, მაგრამ მინიმუმის პოვნა O(n);
დაბალანსებული ძებნის ხე: ყველაფერი O(log n)-ში, მაგრამ ეს მძიმე ტექნიკაა ამოცანისთვის, რომელიც მხოლოდ ერთ ბოლოს უყურებს.

ორობითი გროვა მსუბუქი პასუხია: ნახვა O(1)-ში, ჩასმა და ამოღება O(log n)-ში, მიმთითებლების გარეშე, ჩვეულებრივ მასივში. მასზეა აგებული std::priority_queue, Python-ის heapq და Java-ს PriorityQueue, მათი მეშვეობით კი დეიქსტრასა და პრიმის ალგორითმები, მოვლენების სიმულაცია, „k უდიდესი“ ამოცანები და გროვით სორტირება.

02ორი წესი: ფორმა და რიგი

მინ-გროვა ორობითი ხეა ორი წესით:

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

ფორმის წესი მიმთითებლებზე უარის თქმის საშუალებას გვაძლევს. დავნომროთ წვეროები დონე-დონე 0-დან და ჩავწეროთ მასივში: i ინდექსის შვილები 2i+1 და 2i+2 ადგილებზეა, მშობელი კი (i−1)/2-ზე. ნახაზზე 3 დგას 1 ინდექსზე, მისი შვილები 7 და 5 კი 3 და 4 ინდექსებზე. n წვეროიანი სრული ხის სიმაღლე ⌊log₂ n⌋-ია და სწორედ ეს ზღუდავს ქვემოთ აღწერილ ყველა ოპერაციას.

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

7, 3, 9, 1, 5, 8-ისგან აგებული გროვა: ხედ და მასივად.

03ჩასმა: ამოტივტივება

x-ის ჩასასმელად მას მასივის ბოლოში ვამატებთ. ფორმა სრული რჩება, მაგრამ x შეიძლება მშობელზე ნაკლები იყოს. ამიტომ ვაკეთებთ ამოტივტივებას (sift up): სანამ x მშობელზე ნაკლებია, ვცვლით მათ ადგილებს. ყოველი გაცვლა x-ს ერთი დონით მაღლა სწევს და ამ წიბოზე რიგის წესს აღადგენს; დანარჩენი ისედაც წესრიგში იყო.

ჩავსვათ 2 გროვაში [1, 3, 8, 7, 5, 9]: ის 6 ინდექსზე ხვდება, 8-ის ქვეშ. 2 < 8, ვცვლით; ახლა მისი მშობელია 1 და 2 > 1, ვჩერდებით. შედეგი: [1, 3, 2, 7, 5, 9, 8]. თითო დონეზე მაქსიმუმ ერთი გაცვლა, ამიტომ ჩასმა O(log n)-ია.

ნახვა უბრალოდ heap[0]-ია: O(1). C++-ში ეს pq.top()-ია, pq.push(x) კი ზუსტად ამ ამოტივტივებას ასრულებს.

04მინიმუმის ამოღება: ჩაძირვა და გროვით სორტირება

მინიმუმის ამოსაღებად ვიღებთ heap[0]-ს, სათავეში გადაგვაქვს ბოლო ელემენტი და მასივს ვამოკლებთ. ფორმა ისევ წესრიგშია, მაგრამ ახალი სათავე, სავარაუდოდ, ზედმეტად დიდია. ვაკეთებთ ჩაძირვას (sift down): ვადარებთ შვილებს და ვცვლით უმცირეს შვილთან, ვიდრე ორივე შვილზე ≤ არ გახდება ან ფოთოლი არ აღმოჩნდება. უმცირეს შვილთან გაცვლა მნიშვნელოვანია: ის მეორე შვილის მშობელი ხდება და წესი შენარჩუნდება.

[1, 3, 8, 7, 5, 9]-დან: ვიღებთ 1-ს, 9 გადაგვაქვს სათავეში → [9, 3, 8, 7, 5]; 9 > 3, ვცვლით → [3, 9, 8, 7, 5]; 9 > 5, ვცვლით → [3, 5, 8, 7, 9]. O(log n).

ორი დამატება. გროვის აგება ნებისმიერ მასივს O(n)-ში აქცევს გროვად: ჩავძიროთ ყოველი ინდექსი n/2 − 1-დან 0-მდე. გროვით სორტირება აგებს გროვას და n-ჯერ იღებს მინიმუმს: O(n log n), დამატებითი მეხსიერების გარეშე. C++-ში priority_queue<int> მაქს-გროვაა; მინ-გროვა იწერება ასე: priority_queue<int, vector<int>, greater<int>>.

ფასი ერთი შეხედვით

მინიმუმის ნახვაO(1)

ჩასმა (ამოტივტივება)O(log n)

მინიმუმის ამოღება (ჩაძირვა)O(log n)

გროვის აგება მასივიდანO(n)

გროვით სორტირებაO(n log n)

დაიმახსოვრე

გროვა ორ წესს იცავს: სრული ფორმა, რის გამოც ის მასივში ეტევა და შვილები 2i+1 და 2i+2 ადგილებზეა, და მშობელი ≤ შვილები.
ჩასმა ბოლოდან ამოტივტივებს, ამოღება სათავიდან ჩაძირავს; ორივე ერთ გზას ეხება, O(log n).
გროვა გამოიყენე, როცა ხშირად გჭირდება მიმდინარე მინიმუმი ან მაქსიმუმი და არა სრულად დალაგებული რიგი.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე მასივის ზოლს ხის ქვეშ: ხეში ყოველი გაცვლა მასივის ორი უჯრის გაცვლაა. სცადე შენი რიცხვები, მაგალითად კლებადი სია.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

მინ-გროვა (ხე)

მასივის ხედი (შვილები: 2i+1, 2i+2)

ამოღებული (ზრდადობით)

∅

ჩავსვათ 7 ბოლოში (ინდექსი 0). ეს ხეს „სრულად“ ინახავს (მარცხნიდან მარჯვნივ შევსებული, ხვრელების გარეშე).

ფსევდოკოდი

 1 binary min-heap: complete tree stored in an array 2 insert: append at end, then sift-up while < parent 3   (parent of i is at (i-1)/2) 4 peek min = heap[0]           // O(1) 5 extract-min: move last to root, 6   then sift-down while > a child

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

მასივურ წარმოდგენაში სად არიან 4 ინდექსის შვილები?

№2

მინ-გროვაში [1, 3, 8, 7, 5, 9] ჩავსვით 0. სად აღმოჩნდება 0?

№3

მილიონი რიცხვის ნაკადიდან 10 უდიდესი გჭირდება. რომელი მიდგომაა საუკეთესო?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeLast Stone Weight დამწყები↗LeetCodeKth Largest Element in an Array საშუალო↗LeetCodeTop K Frequent Elements საშუალო↗CSESRoom Allocation საშუალო↗LeetCodeFind Median from Data Stream მოწინავე↗