Heap sort array ਤੋਂ ਇੱਕ binary heap ਬਣਾਉਂਦਾ ਹੈ, ਫਿਰ ਬਾਰ ਬਾਰ ਅਧਿਕਤਮ ਕੱਢਦਾ ਹੈ ਤਾਂ ਜੋ ਸਾਜ਼ਿਸ਼ੀ ਕ੍ਰਮ ਪੈਦਾ ਹੋਵੇ। ਇਹ O(n log n) ਵਿੱਚ ਚਲਦਾ ਹੈ ਅਤੇ in-place ਹੈ।
ਵਿਚਾਰ
ਇੱਕ max-heap ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ ਮੂਲ ਵਿਖੇ ਰੱਖਦਾ ਹੈ। Heap ਬਣਾਓ (O(n)), ਫਿਰ ਮੂਲ ਨੂੰ ਅੰਤ ਵਿੱਚ ਬਦਲੋ, heap ਨੂੰ ਸੁੰਗੜੋ, ਅਤੇ re-heapify (sift down) ਕਰੋ — n ਵਾਰ।
ਉਦਾਹਰਣ
heapq
():
heapq.heapify(arr)
[heapq.heappop(arr)
_ ((arr))]
heap_sort([, , , , ])
