Heap sort வரிசையிலிருந்து binary heap கட்டியெழுப்பி, பிறகு அதிகபட்சத்தை மீண்டும் மீண்டும் பிரித்தெடுத்து வரிசைப்படுத்தப்பட்ட வரிசையை உৎপादிக்கிறது. இது O(n log n) இல் இயங்குகிறது மற்றும் இடத்தில் செயல்படுகிறது.
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 செய்வதன் மூலம் இதை இடத்தில் செய்கிறது.
உத்தரவாதம் O(n log n) மற்றும் O(1) கூடுதல் நினைவாக தேவைப்படும் போது பயன்படுத்தவும் (merge sort க்கு O(n) தேவை; quicksort ஆபத்து O(n²)). இது நிலையற்றது மற்றும் பற்றாக்குறைவான cache locality ஐ கொண்டுள்ளது, எனவே இது நடைமுறையில் quicksort ஐ விட மெதுவாக இருக்கும். அதே heap priority queues மற்றும் top-k உறுப்புகளை கண்டுபிடிப்பதை சக்தியளிக்கிறது.
Heap sort என்பது சாதாரண வரிசையாக்கல்களில் ஒரே ஒன்றாகும், இது மோசமான சந்தர்ப்பம் O(n log n) மற்றும் இடத்தில் இருக்கும், இது நினைவகத்திற்கு வரம்பற்ற அல்லது உத்தரவாதம் வடிவமைப்புகளில் மূল்யவானதாக இருக்கிறது.
Heap கட்டமைப்பு பரவலாக பயனுள்ளதாக உள்ளது — priority queues, Dijkstra இன் வழிமுறை மற்றும் streaming top-k.
சரியான தரவு கட்டமைப்பு ஒரு வழிமுறையை திறமையாக செய்கிறது என்ற கருத்தை இது உறுதி செய்கிறது.