Algorithms #3 ver.2 - better

May 20th, 2022 (edited)
265
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import random
2. import sys
3.
4.
5. class Heap():
6.
7.     def __init__(self, array):
8.         self.array = []  # tuple (key, value)
9.         self.pos = {}  # position of key in array
10.         self.size = len(array)  # number of elements in min heap
11.         for i, item in enumerate(array):
12.             self.array.append((item[0], item[1]))
13.             self.pos[item[0]] = i
14.         for i in range(self.size // 2, -1, -1):
15.             self.heapify(i)
16.
17.         # display items of heap
18.     def display(self):
19.         print('Min array =', end=' ')
20.         for i in range(self.size):
21.             print(f'({self.array[i][0]} : {self.array[i][1]})', end=' ')
22.         print()
23.     # is heap empty ?
24.
25.     def isEmpty(self):
26.         return self.size == 0
27.     # i is an array index
28.     # modify array so that i roots a heap, down-heap
29.
30.     def heapify(self, i):
31.         smallest = i
32.         le = 2 * i + 1
33.         ri = 2 * i + 2
34.         if le < self.size and self.array[le][1] < self.array[smallest][1]:
35.             smallest = le
36.         if ri < self.size and self.array[ri][1] < self.array[smallest][1]:
37.             smallest = ri
38.         if smallest != i:
39.             # update pos
40.             self.pos[self.array[smallest][0]] = i
41.             self.pos[self.array[i][0]] = smallest
42.             # swap
43.             self.array[smallest], self.array[i] = self.array[i], self.array[smallest]
44.             self.heapify(smallest)
45.
46.     # return the min element of the heap
47.     def getMin(self):
48.         if self.size == 0:
49.             return None
50.         return self.array[0]
51.
52.     # return and remove the min element of the heap
53.     def pop(self):
54.         if self.size == 0:
55.             return None
56.         root = self.array[0]
57.         lastNode = self.array[self.size - 1]
58.         self.array[0] = lastNode
59.         del self.array[self.size - 1]
60.         # update pos
61.         self.pos[lastNode[0]] = 0
62.         del self.pos[root[0]]
63.         self.size -= 1
64.         self.heapify(0)
65.         return root
66.
67.     # item (key, value) to push
68.     # modify array to include item
69.     def push(self, item):
70.         # push an item at the end with big value
71.         if self.size < len(self.array):
72.             self.array[self.size] = (item[0], float('inf'))
73.         else:
74.             self.array.append((item[0], float('inf')))
75.         self.pos[item[0]] = self.size
76.         self.size += 1
77.         self.decreaseKey(item)
78.
79.     # decrease value of item (key, value)
80.     # with value smaller than current
81.     def decreaseKey(self, item):
82.         i = self.pos[item[0]]
83.         val = item[1]
84.         # new value must be smaller than current
85.         if self.array[i][1] <= val:
86.             return
87.         self.array[i] = item
88.         # check if is smaller than parent
89.         p = (i - 1) // 2
90.         while i > 0 and self.array[i][1] < self.array[p][1]:
91.             # update pos
92.             self.pos[self.array[i][0]] = p
93.             self.pos[self.array[p][0]] = i
94.             # swap
95.             self.array[p], self.array[i] = self.array[i], self.array[p]
96.             i = p
97.             p = (i - 1) // 2
98.
99.     # increase value of item (key, value),
100.     # with value greater than current
101.     def increaseKey(self, item):
102.         i = self.pos[item[0]]
103.         val = item[1]
104.         # new value must be greater than current
105.         if self.array[i][1] >= val:
106.             return None
107.         self.array[i] = item
108.         # check children
109.         self.heapify(i)
110.
111.     # change value of item (key, value),
112.     # decreaseKey or increaseKey, Running Time: O(log n)
113.     def changeKey(self, item):
114.         i = self.pos[item[0]]
115.         val = item[1]
116.         if val < self.array[i][1]:
117.             self.decreaseKey(item)
118.         if val > self.array[i][1]:
119.             self.increaseKey(item)
120.
121.     # check if exists an item with key = key
122.     def isInHeap(self, key):
123.         if self.pos.get(key) == None:
124.             return False
125.         if self.pos[key] < self.size:
126.             return True
127.         return False
128.
129.     # get the value of item with key = key
130.     def getValueMinHeap(self, key):
131.         if self.pos.get(key) == None:
132.             return None
133.         if self.pos[key] < self.size:
134.             return self.array[self.pos[key]][1]
135.         return None
136.
137.     # This function deletes key at index i. It first reduces
138.     # value to minus infinite and then calls pop()
139.     def deleteKey(self, item):
140.         self.decreaseKey((item[0], float('-inf')))
141.         self.pop()
142.
143.
144. class Problem():
145.     def __init__(self):
146.         self.maxHeap = Heap([])
147.         self.minHeap = Heap([])
148.
150.         if self.maxHeap.isInHeap(i):
151.             self.maxHeap.changeKey((i[0], i[1]))
152.             return
153.         elif self.minHeap.isInHeap(i):
154.             self.minHeap.changeKey((i[0], i[1]))
155.             return
156.         if not self.maxHeap.array or i[1] < -self.maxHeap.array[0][1]:
157.             self.maxHeap.push((i[0], -i[1]))
158.         else:
159.             self.minHeap.push(i)
160.
161.     def balance(self):
162.         if self.minHeap.size - self.maxHeap.size >= 2:
163.             temp = self.minHeap.pop()
164.             self.maxHeap.push((temp[0], -temp[1]))
165.         elif self.maxHeap.size - self.minHeap.size >= 2:
166.             temp = self.maxHeap.pop()
167.             self.minHeap.push((temp[0], -temp[1]))
168.
169.     def median(self):
170.         # print('Max heap:\t{}\nMin heap:\t{}'.format(
171.         #    self.maxHeap.array, self.minHeap.array))
172.         if self.minHeap.size == self.maxHeap.size:
173.             return ((self.minHeap.array[0][1] - self.maxHeap.array[0][1]) / 2)
174.         elif self.minHeap.size > self.maxHeap.size:
175.             return float(self.minHeap.array[0][1])
176.         else:
177.             return float(-self.maxHeap.array[0][1])
178.
179.
180. if __name__ == '__main__':
181.     prob = Problem()
182.     random.seed()
183.     for i in range(500000):