Heap sort अॅरे पासून binary heap तयार करते, नंतर क्रमवारीत क्रमाची निर्मिती करण्यासाठी जास्तीत जास्त वारंवार काढून घेते. हे O(n log n) मध्ये चालते आणि in-place आहे.
Max-heap मूळ येथे सर्वात मोठा घटक ठेवते. Heap तयार करा (O(n)), नंतर मूळ शेवटी स्वॅप करा, 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]
क्लासिक अंमलीकरण हे अॅरे मध्ये sift down करून in-place मध्ये करते.
जेव्हा आपल्याला गॅरेंटीड 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, Dijkstra चा अल्गोरिदम, आणि streaming top-k.
हे कल्पना स्थापित करते की योग्य डेटा रचना अल्गोरिदम कार्यक्षम बनवते.
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या