Heap sort — in-place

Heap sort max-heap ஐ பயன்படுத்தி இடத்தில் (in-place) வரிசைப்படுத்துகிறது: மிகப் பெரியதை முனையிலிருந்து எடுத்து முடிவில் பொருத்தி heap சுருக்குதல். மோசமான சூழலிலும் O(n log n); merge sort போல் கூடுதல் அணி தேவையில்லை.

உண்மை உலகில் இது ஏன் முக்கியம்?

உட்பொதிந்த விமான கட்டுப்பாட்டு அமைப்புகளில் பெரிய கூடுதல் அணி இல்லாமல் — heap sort பொருந்தும். தரவுத்தளம் வரம்பிட்ட நினைவகத்தில் top-K, heap இயந்திரம். ஏற்கனவே priority queue பயன்படுத்தும் இடங்களில் heap sort தொடர்பு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

கீழிருந்து heapify செய்து max-heap O(n). வேர் a[0] ஐ a[n-1] உடன் பரிமாற்றி heap அளவைக் குறைத்து வேரை மூழ்கடி (sink). மீண்டும். வலது முனை sorted. quicksort மோசமான சூழலை விட இங்கு உயரம் log; ஆனால் cache சில நேரங்களில் மோசம்.

Pythonில் முயற்சி செய்வோம்

import heapq


def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]


print(heapsort([3, 1, 4, 1, 5]))

அடிக்கடி நேரும் தவறுகள்

• sink இல் heap அளவு ஒற்றைப் பிழை.
• min/max குழப்பம்.
• பாடப்புத்தக மாறுபாடு பொதுவாக stable அல்ல.

முக்கியச் சுருக்கக் குறிப்புகள்

• O(n log n), O(1) கூடுதல் இடம்.
• quicksort ஐ விட மோசமான மாறிலி, ஆனால் மோசமான சூழல் கணிக்கத்தக்கது.
• priority queue ↔ வரிசை கோட்பாடு பாலம்.