diff options
Diffstat (limited to 'progs/a339.py')
| -rw-r--r-- | progs/a339.py | 25 |
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
|