Init

1 files changed, 25 insertions, 0 deletions

diff --git a/progs/a339.py b/progs/a339.py
new file mode 100644
index 0000000..9a57403
--- /dev/null
+++ b/progs/a339.py
@@ -0,0 +1,25 @@
+def heap_sort(arr):

+    heapify(arr)  

+    end = len(arr) - 1

+    while end > 0:

+        arr[end], arr[0] = arr[0], arr[end]

+        shift_down(arr, 0, end - 1)

+        end -= 1

+    return arr

+

+def heapify(arr):

+    start = len(arr) // 2

+    while start >= 0:

+        shift_down(arr, start, len(arr) - 1)

+        start -= 1

+def shift_down(arr, start, end):

+    root = start

+    while root * 2 + 1 <= end:

+        child = root * 2 + 1

+        if child + 1 <= end and arr[child] < arr[child + 1]:

+            child += 1

+        if child <= end and arr[root] < arr[child]:

+            arr[root], arr[child] = arr[child], arr[root]

+            root = child

+        else:

+            return