რა არის სტეკი (მონაცემთა სტრუქტურების კონტექსტში)?

Heap — ეს სპეციალიზებული ხეია, რომელიც გამოიყენება მონაცემთა სტრუქტურად. ჰიპის ძირითადი თვისება — ნაწილობრივი წესრიგი: ნებისმიერი კვანძისთვის შესრულებულია პირობა, რომ მშობლის მნიშვნელობა მეტია ან ტოლია მისი შვილების მნიშვნელობებზე (max-heap) ან ნაკლები ან ტოლია (min-heap).

ძირითადი მახასიათებლები:

• ბინარული ხე: ყველაზე ხშირად რეალიზებულია ბინარული ხის სახით, სადაც თითოეულ კვანძს მაქსიმუმ ორი შვილი აქვს.
• სრული ბინარული ხე: ყველა დონეზე, გარდა შესაძლოა ბოლო, ხე სრულად არის სავსე. ბოლო დონეზე კვანძები იწერება მარცხნიდან მარჯვნივ. ეს საშუალებას აძლევს ეფექტურად შეინახოთ ჰიპი მასივის სახით.
• ჰიპის თვისება:
  • Max-heap: თითოეული კვანძის მნიშვნელობა მეტია ან ტოლია მისი შვილების მნიშვნელობებზე. ყველაზე დიდი ელემენტი ყოველთვის მდებარეობს ძირის წერტილში.
  • Min-heap: თითოეული კვანძის მნიშვნელობა ნაკლებია ან ტოლია მისი შვილების მნიშვნელობებზე. ყველაზე პატარა ელემენტი ყოველთვის მდებარეობს ძირის წერტილში.

ჰიპის ოპერაციები:

• ელემენტის დამატება: ახალი ელემენტის დამატება და ჰიპის თვისების შენარჩუნება.
• ელემენტის წაშლა: ძირის ელემენტის (ყველაზე დიდი ან ყველაზე პატარა — ჰიპის ტიპზე დამოკიდებული) წაშლა და ჰიპის თვისების შენარჩუნება.
• ჰიპის შექმნა: მასივიდან ჰიპის აგება.

ჰიპის გამოყენება:

• სორტირება: Heapsort ალგორითმი.
• პრიორიტეტული რიგები: ეფექტური რეალიზაცია, სადაც ელემენტები მუშავდება პრიორიტეტით.
• ძებნის ალგორითმები: მაგალითად, k-მე ყველაზე დიდი ელემენტის ძიება.
• გრაფის ალგორითმები: მაგალითად, Dijkstra-ს ალგორითმი.

ჰიპის წარმოდგენა მასივით:

მიუხედავად იმისა, რომ ჰიპი არის სრული ბინარული ხე, ის ეფექტურად შეიძლება შენახულ იქნას მასივში ინდექსების გარეშე.

• თუ კვანძი მდებარეობს ინდექსზე i, მისი მარცხენა შვილი მდებარეობს ინდექსზე 2*i + 1.
• მისი მარჯვენა შვილი მდებარეობს ინდექსზე 2*i + 2.
• მისი მშობელი მდებარეობს ინდექსზე (i - 1) / 2.

# მინ-ჰიპის მასივის მაგალითი
heap_array = [10, 15, 20, 17, 25, 30]

# ძირი: heap_array[0] = 10
# მარცხენა შვილი: heap_array[2*0 + 1] = heap_array[1] = 15
# მარჯვენა შვილი: heap_array[2*0 + 2] = heap_array[2] = 20
# მშობელი ინდექსზე 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15