Python-Interview-Problems-for-Practice/heap_structure.py at master · devAmoghS/Python-Interview-Problems-for-Practice · GitHub

Name: Python-Interview-Problems-for-Practice/heap_structure.py at master · devAmoghS/Python-Interview-Problems-for-Practice · GitHub
Rating: 4.4 (7140 reviews)
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
classHeap(object):

HEAP_SIZE=10

def__init__(self):
self.heap= [0] *Heap.HEAP_SIZE
self.currentPosition=-1

definsert(self, item):

# if heap is full , we print a notification
ifself.isFull():
print("Heap is full")
return
# else, increment the currentPosition and add item
self.currentPosition+=1
self.heap[self.currentPosition] =item
self.fixUp(self.currentPosition)

deffixUp(self, index):
parentIndex=int((index-1) /2)
whileparentIndex>=0andself.heap[parentIndex] <self.heap[index]:
# if True swap heap[index] and heap[parentIndex]
temp=self.heap[index]
self.heap[index] =self.heap[parentIndex]
self.heap[parentIndex] =temp
# update the index and parentIndex
index=parentIndex
parentIndex=int((index-1) /2)

deffixDown(self, index, upto):
ifupto<0:
upto=self.currentPosition

whileindex<=upto:
leftChild=2*index+1
rightChild=2*index+2

ifleftChild<=upto:
childToSwap=0
else:
ifself.heap[leftChild] <self.heap[rightChild]:
childToSwap=leftChild
else:
childToSwap=rightChild

ifself.heap[index] <self.heap[childToSwap]:
temp=self.heap[index]
self.heap[index] =self.heap[childToSwap]
self.heap[childToSwap] =temp
else:
break

index=childToSwap

else:
return

defheapSort(self):
foriinrange(0, self.currentPosition+1):
temp=self.heap[0]
print("%d"%temp)
self.heap[0] =self.heap[self.currentPosition-i]
self.heap[self.currentPosition-i] =temp
self.fixDown(0, self.currentPosition-i-1)

defgetMax(self):
result=self.heap[0]
self.currentPosition-=1
self.heap[0] =self.heap[self.currentPosition]
delself.heap[self.currentPosition]
self.fixDown(0, -1)
returnresult

defisFull(self):
returnself.currentPosition==Heap.HEAP_SIZE


some_heap=Heap()
some_heap.insert(12)
some_heap.insert(-3)
some_heap.insert(21)
some_heap.insert(7)
some_heap.insert(4)
some_heap.heapSort()