5. Min Heap

Main Heap¶

References:¶

1. https://favtutor.com/blogs/heap-in-python

To-do:

1. One more way of implementing this is keep inserting into a list and at the end call build heap function
2. correct print_heap
3. implement delete node

In [1]:

from typing import List

from typing import List

In [8]:

class MinHeap:
    def __init__(self, arr: List) -> None:
        self.heap = arr
        self.size = len(self.heap)

    def min_heapify(self, i):
        # print("came")
        smallest = i

        left_child_idx = (2 * i) + 1
        right_child_idx = (2 * i) + 2

        if left_child_idx < self.size and self.heap[left_child_idx] < self.heap[i]:
            smallest = left_child_idx
        else:
            smallest = i

        if (
            right_child_idx < self.size
            and self.heap[right_child_idx] < self.heap[smallest]
        ):
            smallest = right_child_idx

        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.min_heapify(smallest)

    def build_heap(self):

        for i in range((self.size // 2) - 1, -1, -1):
            self.min_heapify(i)

class MinHeap: def __init__(self, arr: List) -> None: self.heap = arr self.size = len(self.heap) def min_heapify(self, i): # print("came") smallest = i left_child_idx = (2 * i) + 1 right_child_idx = (2 * i) + 2 if left_child_idx < self.size and self.heap[left_child_idx] < self.heap[i]: smallest = left_child_idx else: smallest = i if ( right_child_idx < self.size and self.heap[right_child_idx] < self.heap[smallest] ): smallest = right_child_idx if smallest != i: self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] self.min_heapify(smallest) def build_heap(self): for i in range((self.size // 2) - 1, -1, -1): self.min_heapify(i)

In [17]:

arr = list(reversed(range(10)))
arr = [3, 9, 2, 1, 4, 5]
heap = MinHeap(arr)

heap.build_heap()

arr = list(reversed(range(10))) arr = [3, 9, 2, 1, 4, 5] heap = MinHeap(arr) heap.build_heap()

In [18]:

heap.heap

heap.heap

Out[18]:

[1, 3, 2, 9, 4, 5]

In [16]:

import heapq

lst = [8, 6, 7, 4, 1, 0, 3, 2]
lst = [3, 9, 2, 1, 4, 5]
# lst = list(range(10))
heapq.heapify(lst)
print(lst)

import heapq lst = [8, 6, 7, 4, 1, 0, 3, 2] lst = [3, 9, 2, 1, 4, 5] # lst = list(range(10)) heapq.heapify(lst) print(lst)

[1, 3, 2, 9, 4, 5]

In [ ]: