-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeaps.py
More file actions
91 lines (74 loc) · 2.21 KB
/
Heaps.py
File metadata and controls
91 lines (74 loc) · 2.21 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
# This file demonstrate the implementation of Heap in pyhton using the
# python list,
'''
A Heap is a data structure whic satisfies the heap property. the Heap property
states that there must be certain relationship between a parent node and its child
node. The property must apply through the entire heap
In a MIN HEAP the relationship between parent and children is that the parent must always
be less than or equal to its children. As a consequence ot this, the lowest element in
the heap must be the root node
In a MAX HEAP, The parent is greate than or equal to its child or its children. It
follows from this that the largest value makes up the root node
'''
#for the sake of simpliciyt of calculat of parent and child node the
# the 0th index of list has been filled with zero.
class Heap:
def __init__(self):
self.heap = [0]
self.count = 0
def _float(self, index):
'''
Makes sure the min Heap is maintained by moving up the recently
added value up the heap structure , till when its parent is less than its
children
'''
k = index
while k//2 > 0:
# checks if the parent is greater than the child
if self.heap[k//2] > self.heap[k]:
self.heap[k//2], self.heap[k] = self.heap[k] ,self.heap[k//2]
else:
break
k = k//2
def insert(self, value):
self.heap.append(value)
self.count += 1
self._float(self.count)
def _min(self, k):
if k*2 +1 > self.count:
return k*2
elif self.heap[k*2] < self.heap[k*2 +1]:
return k*2
else:
return k*2 +1
def _sink(self):
k = 1
while k*2 <= self.count:
min_index = self._min(k)
if self.heap[k] > self.heap[min_index]:
self.heap[k] , self.heap[min_index] = self.heap[min_index], self.heap[k]
else:
break
k = min_index
def pop(self):
'''
Pop on a min heap always return the smalles value in the heap
in our case it will at '1' index of the heap. After that heap
needs to be re-balanced to maintain its min heap structure.
'''
value = self.heap[1]
self.heap[1] = self.heap[self.count]
self.count -= 1
self.heap.pop()
self._sink()
return value
def test():
h = Heap()
for i in (4,8,7,2,9,10,5,1,3,6):
h.insert(i)
print(h.heap)
while len(h.heap)>1:
n = h.pop()
print(n)
print(h.heap)
test()