forked from OmkarPathak/Data-Structures-using-Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheapsort.py
More file actions
32 lines (24 loc) · 983 Bytes
/
heapsort.py
File metadata and controls
32 lines (24 loc) · 983 Bytes
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
def heapify(nums, heap_size, root_index):
# Assume the index of the largest element is the root index
largest = root_index
left_child = (2 * root_index) + 1
right_child = (2 * root_index) + 2
if left_child < heap_size and nums[left_child] > nums[largest]:
largest = left_child
if right_child < heap_size and nums[right_child] > nums[largest]:
largest = right_child
if largest != root_index:
nums[root_index], nums[largest] = nums[largest], nums[root_index]
# Heapify the new root element to ensure it's the largest
heapify(nums, heap_size, largest)
def heap_sort(nums):
n = len(nums)
for i in range(n, -1, -1):
heapify(nums, n, i)
# Move the root of the max heap to the end of
for i in range(n - 1, 0, -1):
nums[i], nums[0] = nums[0], nums[i]
heapify(nums, i, 0)
random_list_of_nums = [35, 12, 43, 8, 51]
heap_sort(random_list_of_nums)
print(random_list_of_nums)