10 examples of 'min heap in python' in Python

Every line of 'min heap in python' code snippets is scanned for vulnerabilities by our powerful machine learning engine that combs millions of open source libraries, ensuring your Python code is secure.

All examples are scanned by Snyk Code

By copying the Snyk Code Snippets you agree to
this disclaimer
68def min_heapify(self, i):
69 l = self.left(i)
70 r = self.right(i)
71 if (l <= (self.heap_size - 1)) and (self[l] < self[i]):
72 smallest = l
73 else:
74 smallest = i
75 if (r <= (self.heap_size - 1)) and (self[r] < self[smallest]):
76 smallest = r
77 if smallest != i:
78 self[i], self[smallest] = self[smallest], self[i]
79 self.min_heapify(smallest)
Important

Use secure code every time

Secure your code as it's written. Use Snyk Code to scan source code in minutes – no build needed – and fix issues immediately. Enable Snyk Code

47def min_heap_sort(arr, simulation=False):
48 """ Heap Sort that uses a min heap to sort an array in ascending order
49 Complexity: O(n log(n))
50 """
51 iteration = 0
52 if simulation:
53 print("iteration",iteration,":",*arr)
54
55 for i in range(0, len(arr) - 1):
56 iteration = min_heapify(arr, i, simulation, iteration)
57
58 return arr
164def downheap(self):
165 tmp = 0
166 i = 0
167 while True:
168 left = (i << 1) + 1;
169 right = left + 1;
170 if left >= self.nheap:
171 return
172 if right >= self.nheap:
173 if self.heap[i] < self.heap[left]:
174 tmp = self.heap[left]
175 self.heap[left] = self.heap[i]
176 self.heap[i] = tmp
177 return
178
179 if self.heap[i] >= self.heap[left] and self.heap[i] >= self.heap[right]:
180 return
181
182 if self.heap[left] > self.heap[right]:
183 tmp = self.heap[left]
184 self.heap[left] = self.heap[i]
185 self.heap[i] = tmp
186 i = left
187 else:
188 tmp = self.heap[right]
189 self.heap[right] = self.heap[i]
190 self.heap[i] = tmp
191 i = right
171def test_find_min_when_heap_has_random_size(self):
172 a = [randint(-100, 100) for _ in range(3, 100)]
173 h = MinMaxHeap(a)
174 self.assertEqual(h.find_min(), min(a))
112def build_heap(arr, heapType):
113 if heapType == "MAX_HEAP":
114 new_heap = MaxHeap()
115 else:
116 new_heap = MinHeap()
117 new_heap.size = len(arr)
118 new_heap.heap = [0] + arr
119 i = len(arr) // 2
120 while i > 0:
121 new_heap.perc_down(i)
122 i-=1
123 return new_heap
51def max_heapify(ls: list, heap_size: int, i: int) -> None:
52 """This operation is also sometimes called `push_down`, `shift_down` or `bubble_down`.
53
54 Time complexity: O(log(n))."""
55 m = i
56 left = 2 * i + 1
57 right = 2 * i + 2
58 if left < heap_size and ls[left] > ls[m]:
59 m = left
60 if right < heap_size and ls[right] > ls[m]:
61 m = right
62 if i != m:
63 ls[i], ls[m] = ls[m], ls[i]
64 max_heapify(ls, heap_size, m)
6def test_min_heap(self):
7 heap = MinHeap()
8 assert_equal(heap.peek_min(), None)
9 assert_equal(heap.extract_min(), None)
10 heap.insert(20)
11 assert_equal(heap.array[0], 20)
12 heap.insert(5)
13 assert_equal(heap.array[0], 5)
14 assert_equal(heap.array[1], 20)
15 heap.insert(15)
16 assert_equal(heap.array[0], 5)
17 assert_equal(heap.array[1], 20)
18 assert_equal(heap.array[2], 15)
19 heap.insert(22)
20 assert_equal(heap.array[0], 5)
21 assert_equal(heap.array[1], 20)
22 assert_equal(heap.array[2], 15)
23 assert_equal(heap.array[3], 22)
24 heap.insert(40)
25 assert_equal(heap.array[0], 5)
26 assert_equal(heap.array[1], 20)
27 assert_equal(heap.array[2], 15)
28 assert_equal(heap.array[3], 22)
29 assert_equal(heap.array[4], 40)
30 heap.insert(3)
31 assert_equal(heap.array[0], 3)
32 assert_equal(heap.array[1], 20)
33 assert_equal(heap.array[2], 5)
34 assert_equal(heap.array[3], 22)
35 assert_equal(heap.array[4], 40)
36 assert_equal(heap.array[5], 15)
37 mins = []
38 while heap:
39 mins.append(heap.extract_min())
40 assert_equal(mins, [3, 5, 15, 20, 22, 40])
41 print('Success: test_min_heap')
219def smallest_child(self,k):
220 '''
221 return the index of smallest child of K
222 @precondition: 2*k <= self.count (has at least 1 child)
223 '''
224 if 2*k == self.count or self.array[2*k] < self.array[2*k+1]:
225 return 2*k
226 else:
227 return 2*k+1
180def test_remove_min_when_heap_has_size_1(self):
181 h = MinMaxHeap([13])
182 self.assertEqual(h.remove_min(), 13)
183 self.assertTrue(h.is_empty())
184 self.assertEqual(h.size, 0)
11def heappushpop(heap: List[_T], item: _T) -> _T: pass

Related snippets