10 examples of 'min heap in python' in Python

68
def 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)

47
def 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

164
def 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

171
def 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))

112
def 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

51
def 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)

6
def 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')

219
def 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

180
def 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)

11
def heappushpop(heap: List[_T], item: _T) -> _T: pass