Heap sort აგებს ორობითი heap-ს მასივიდან, შემდეგ განმეორებით იღებს მაქსიმუმს დასალაგებელი თანმიმდევრობის წამოსახდებად. ის მუშაობს O(n log n) დროში და არის in-place.
Max-heap ინახავს ყველაზე დიდ ელემენტს root-ში. აირჩიე heap (O(n)), შემდეგ შეცვალე root ბოლოში, შეამცირე heap და გადააკეთე-heapify (sift down) — n ჯერ.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
კლასიკური განხორციელება ამას აკეთებს in-place-ში, მასივში sift down-ის გამოყენებით.
გამოიყენე როდესაც გჭირდებათ გარანტირებული O(n log n) და O(1) დამატებითი მეხსიერება (merge sort მოითხოვს O(n); quicksort რისკავს O(n²)). ეს არ არის სტაბილური და აქვს ცუდი cache locality, ამიტომ ხშირად ნელი არის პრაქტიკაში quicksort-ზე. იგივე heap-ი ხელმძღვანელობს priority queue-ებს და top-k ელემენტების პოვნას.
Heap sort არის ერთადერთი საერთო სორტი, რომელიც არის worst-case O(n log n) და in-place, რაც მას ღირებულს ხდის მეხსიერებით შეზღუდულ ან გარანტირებული-შეკრულ პარამეტრებში.
ქვემოთ heap სტრუქტურა ფართოდ სასარგებლოა — priority queue-ები, დიჯკსტრას ალგორითმი, და streaming top-k.
ეს ამყარებს იდეას, რომ სწორი მონაცემთა სტრუქტურა ალგორითმს ეფექტიან ხდის.
IT გასაუბრების კითხვების ბიბლიოთეკა დეტალური პასუხებით — Junior-დან Senior-მდე.
შემოწირულობა