Heap sort array سے ایک binary heap بناتا ہے، پھر بار بار maximum نکال کر sorted ترتیب بناتا ہے۔ یہ O(n log n) میں چلتا ہے اور in-place ہے۔
ایک max-heap سب سے بڑے عنصر کو root میں رکھتا ہے۔ Heap بنائیں (O(n))، پھر root کو آخر میں swap کریں، heap کو سکیڑیں، اور re-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]
ایک classic implementation اسے array کے اندر sift down کر کے in place کرتا ہے۔
استعمال کریں جب آپ کو guaranteed O(n log n) اور O(1) extra memory کی ضرورت ہو (merge sort کو O(n) چاہیے؛ quicksort کو O(n²) کا خطرہ)۔ یہ stable نہیں ہے اور cache locality خراب ہے، تو عملی طور پر اکثر quicksort سے سست ہے۔ یہی heap priority queues اور top-k عناصر تلاش کرنے میں بھی کام آتا ہے۔
Heap sort واحد عام sort ہے جو worst-case O(n log n) اور in-place دونوں ہے، یہ memory-constrained یا guaranteed-bound حالات میں قیمتی ہے۔
اس کے نیچے heap ساخت وسیع طور پر مفید ہے — priority queues، Dijkstra's algorithm، اور streaming top-k۔
یہ اس خیال کو مضبوط کرتا ہے کہ صحیح data structure ایک algorithm کو موثر بناتا ہے۔
تفصیلی جوابات کے ساتھ IT انٹرویو سوالات کی ایک لائبریری — جونیئر سے سینئر تک۔
عطیہ دیں