diff options
author | Egor Tensin <Egor.Tensin@gmail.com> | 2019-12-23 07:32:18 +0300 |
---|---|---|
committer | Egor Tensin <Egor.Tensin@gmail.com> | 2019-12-23 07:32:18 +0300 |
commit | 0d25b5d6957d76bab486e2279c99e130c19d5c31 (patch) | |
tree | c8c7d6fe4766470bda03e49a004afaa03c967b16 /algorithms/impl/heapsort.py | |
parent | Travis: add badge to README (diff) | |
download | sorting-algorithms-0d25b5d6957d76bab486e2279c99e130c19d5c31.tar.gz sorting-algorithms-0d25b5d6957d76bab486e2279c99e130c19d5c31.zip |
pylint/pep8 fixes
Diffstat (limited to 'algorithms/impl/heapsort.py')
-rw-r--r-- | algorithms/impl/heapsort.py | 11 |
1 files changed, 11 insertions, 0 deletions
diff --git a/algorithms/impl/heapsort.py b/algorithms/impl/heapsort.py index bf9f464..81bea20 100644 --- a/algorithms/impl/heapsort.py +++ b/algorithms/impl/heapsort.py @@ -9,6 +9,7 @@ from ..algorithm import SortingAlgorithm # Disclaimer: implemented in the most literate way. + def heapsort(xs): _heapify(xs) first, last = 0, len(xs) - 1 @@ -17,26 +18,32 @@ def heapsort(xs): _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: @@ -54,18 +61,22 @@ def _siftdown(xs, start, end): else: break + _ALGORITHMS = [ SortingAlgorithm('heapsort', 'Heapsort', heapsort), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(heapsort(list(xs))) + if __name__ == '__main__': main() |