რა არის ბეჭედი?

ხეიფი (heap) არის განსაკუთრებული ხის სტრუქტურა მონაცემთა, რომელიც აკმაყოფილებს ხეიფის თვისებას. ეს თვისება ამბობს, რომ ნებისმიერი კვანძისთვის, გარდა ფესვის, ამ კვანძის გასაღების მნიშვნელობა უნდა იყოს გარკვეულ ურთიერთობაში მისი მშობლის მნიშვნელობასთან. არსებობს ორი ძირითადი ტიპის ხეიფი:

• მაქს-ხეიფი (Max-heap): თითოეული კვანძის გასაღების მნიშვნელობა არ არის ნაკლები მისი შვილების მნიშვნელობებზე. მაქსიმალური ელემენტი მდებარეობს ფესვში.
• მინ-ხეიფი (Min-heap): თითოეული კვანძის გასაღების მნიშვნელობა არ არის მეტი მისი შვილების მნიშვნელობებზე. მინიმალური ელემენტი მდებარეობს ფესვში.

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

• i ინდექსზე მყოფი ელემენტისათვის (0-დან იწყება), მისი მარცხენა შვილი მდებარეობს ინდექსზე 2i + 1.
• მისი მარჯვენა შვილი მდებარეობს ინდექსზე 2i + 2.
• მისი მშობელი მდებარეობს ინდექსზე floor((i - 1) / 2).

ძირითადი ოპერაციები ხეიფზე:

• Insert (ჩამატება): ახალი ელემენტის დამატება. დროის სირთულე O(log n), სადაც n ელემენტების რაოდენობაა.
• Extract-Max / Extract-Min: მაქსიმუმის (max-ხეიფში) ან მინიმუმის (min-ხეიფში) ელემენტის წაშლა და დაბრუნება. დროის სირთულე O(log n).
• Heapify (ხეიფის აგება): ნებისმიერი მასივის გარდაქმნა ხეიფად. დროის სირთულე O(n).

ხეიფები გამოიყენება სორტირების ალგორითმებში (მაგალითად, heapsort), პრიორიტეტული რიგებში და მოკლე გზების ძებნის ალგორითმებში (მაგალითად, Dijkstra-ის ალგორითმი).