From 2183f3f860af34e45058ef078045322062b51f42 Mon Sep 17 00:00:00 2001 From: Egor Tensin Date: Sun, 17 Apr 2016 00:49:33 +0300 Subject: rearrange source files * Add a useful `algorithms` package to provide convinient access to the implemented algorithms. * This allows to e.g. dynamically list available algorithms, which greatly simplifies a lot of things. --- heapsort.py | 54 ------------------------------------------------------ 1 file changed, 54 deletions(-) delete mode 100644 heapsort.py (limited to 'heapsort.py') diff --git a/heapsort.py b/heapsort.py deleted file mode 100644 index 3f44e51..0000000 --- a/heapsort.py +++ /dev/null @@ -1,54 +0,0 @@ -# Copyright 2015 Egor Tensin -# This file is licensed under the terms of the MIT License. -# See LICENSE.txt for details. - -# Disclaimer: implemented in the most literate way. - -def heapsort(xs): - heapify(xs) - first, last = 0, len(xs) - 1 - for end in range(last, first, -1): - xs[end], xs[first] = xs[first], xs[end] - siftdown(xs, first, end - 1) - return xs - -# In a heap stored in a zero-based array, -# left_child = node * 2 + 1 -# right_child = node * 2 + 2 -# parent = (node - 1) // 2 - -def _get_parent(node): - return (node - 1) // 2 - -def _get_left_child(node): - return node * 2 + 1 - -def _get_right_child(node): - return node * 2 + 2 - -def heapify(xs): - last = len(xs) - 1 - first_parent, last_parent = 0, _get_parent(last) - for parent in range(last_parent, first_parent - 1, -1): - siftdown(xs, parent, last) - -def siftdown(xs, start, end): - root = start - while True: - # We swap if there is at least one child - child = _get_left_child(root) - if child > end: - break - # If there are two children, select the minimum - right_child = _get_right_child(root) - if right_child <= end and xs[child] < xs[right_child]: - child = right_child - if xs[root] < xs[child]: - xs[root], xs[child] = xs[child], xs[root] - root = child - else: - break - -if __name__ == '__main__': - import sys - print(heapsort(list(map(int, sys.argv[1:])))) -- cgit v1.3