-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathheap_sort.py
More file actions
94 lines (73 loc) · 2.51 KB
/
Copy pathheap_sort.py
File metadata and controls
94 lines (73 loc) · 2.51 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
"""
Heap Sort
Heap sort builds a heap from the data and repeatedly extracts the
extreme element to produce a sorted array. Two variants are provided:
max-heap sort and min-heap sort.
Reference: https://en.wikipedia.org/wiki/Heapsort
Complexity:
Time: O(n log n) best / O(n log n) average / O(n log n) worst
Space: O(1)
"""
from __future__ import annotations
def max_heap_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using a max-heap.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> max_heap_sort([3, 1, 2])
[1, 2, 3]
"""
for i in range(len(array) - 1, 0, -1):
_max_heapify(array, i)
return array
def _max_heapify(array: list[int], end: int) -> None:
"""Build a max-heap on *array[0..end]* and swap the root to *end*."""
last_parent = (end - 1) // 2
for parent in range(last_parent, -1, -1):
current = parent
while current <= last_parent:
child = 2 * current + 1
if child + 1 <= end and array[child] < array[child + 1]:
child += 1
if array[child] > array[current]:
array[current], array[child] = array[child], array[current]
current = child
else:
break
array[0], array[end] = array[end], array[0]
def min_heap_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using a min-heap.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> min_heap_sort([3, 1, 2])
[1, 2, 3]
"""
for i in range(len(array) - 1):
_min_heapify(array, i)
return array
def _min_heapify(array: list[int], start: int) -> None:
"""Build a min-heap on *array[start..]* and place the minimum at *start*."""
end = len(array) - 1
last_parent = (end - start - 1) // 2
for parent in range(last_parent, -1, -1):
current = parent
while current <= last_parent:
child = 2 * current + 1
if (
child + 1 <= end - start
and array[child + start] > array[child + 1 + start]
):
child += 1
if array[child + start] < array[current + start]:
array[current + start], array[child + start] = (
array[child + start],
array[current + start],
)
current = child
else:
break