From f05d888a0b621ca4e99e2b0fb6e23c097006fe41 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Tue, 28 May 2024 10:29:13 +0200 Subject: Init --- progs/a339.py | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 progs/a339.py (limited to 'progs/a339.py') 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 -- cgit v1.2.3-18-g5258