Heap Sort example.

shubhmsng
967 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Welcome!

Heap sort.

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
def heapify(a, i, heap_size):
l = 2*i
r = 2*i + 1
if l < heap_size and a[l] > a[i] :
largest = l
else:
largest = i
if r < heap_size and a[r] > a[largest]:
largest = r
if largest != i:
temp = a[i]
a[i] = a[largest]
a[largest] = temp
heapify(a, largest, heap_size)
def build_heap(a, heap_size):
for i in range(int((heap_size-1)/2), 0, -1):
heapify(a, i, heap_size - 1)
a = input().split()
a = [0] + a
a = list(map(int, a))
build_heap(a, len(a))
heap_size = len(a)
for i in range(len(a) -1, 0, -1):
temp = a[i]
a[i] = a[1]
a[1] = temp
heap_size -= 1
heapify(a, 1, heap_size)
a.remove(0)
print(a)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content