एक binary heap एक संपूर्ण बाइनरी ट्री आहे जो अॅरेमध्ये संचयित केला जातो जो heap property राखतो: min-heap मध्ये, प्रत्येक पालक त्याच्या मुलांपेक्षा ≤ असतो, त्यामुळे किमान नेहमी मूलावर असते. हे priority queue चे मानक अंमलबजावणी बनवते.
1 index: 0 1 2 3 4
/ \ array: [1, 3, 5, 8, 4]
3 5 parent(i) = (i-1)//2
/ \ left(i) = 2i+1
8 4 right(i) = 2i+2
import heapq
h = []
heapq.heappush(h, 5) # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # peek min -> O(1)
heapq.heappop(h) # O(log n) — remove root, sift down -> 1
| Operation | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |
हीप तुम्हाला सर्वकाही पूर्णपणे सॉर्ट केल्याशिवाय पुढील सर्वात महत्वाचा घटक तात्काळ देतो, जो पुन्हा सॉर्ट करण्यापेक्षा कितीतरी स्वस्त आहे.
हे प्रायोरिटी-चालित अल्गोरिदमचा आधार आहे आणि "k सर्वात मोठे/सर्वात लहान" प्रश्नांसाठी वारंवार मुलाखत साधन आहे.