2. Binary Heap using heapq

Binary Heap¶

References¶

1. https://www.geeksforgeeks.org/binary-heap/

In [2]:

from heapq import heapify, heappop, heappush

from heapq import heapify, heappop, heappush

In [10]:

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def insert(self, key):
        heappush(self.heap, key)

    def get_min(self):
        return self.heap[0]

    def extract_min(self):
        return heappop(self.heap)

    def decrease_key(self, i, new_value):
        self.heap[i] = new_value
        while i != 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = (
                self.heap[self.parent(i)],
                self.heap[i],
            )

    def delete_key(self, i):
        self.decrease_key(i, float("-inf"))
        self.extract_min()

class MinHeap: def __init__(self): self.heap = [] def parent(self, i): return (i - 1) // 2 def insert(self, key): heappush(self.heap, key) def get_min(self): return self.heap[0] def extract_min(self): return heappop(self.heap) def decrease_key(self, i, new_value): self.heap[i] = new_value while i != 0 and self.heap[self.parent(i)] > self.heap[i]: self.heap[i], self.heap[self.parent(i)] = ( self.heap[self.parent(i)], self.heap[i], ) def delete_key(self, i): self.decrease_key(i, float("-inf")) self.extract_min()

In [11]:

heap = MinHeap()
heap.insert(3)
heap.insert(2)

heap = MinHeap() heap.insert(3) heap.insert(2)

In [12]:

heap.delete_key(1)

heap.delete_key(1)

In [13]:

heap.heap

heap.heap

Out[13]:

[2]

In [14]:

heap.insert(15)
heap.insert(5)
heap.insert(4)
heap.insert(45)

heap.insert(15) heap.insert(5) heap.insert(4) heap.insert(45)

In [15]:

heap.heap

heap.heap

Out[15]:

[2, 4, 5, 15, 45]

In [16]:

heap.extract_min()

heap.extract_min()

Out[16]:

2

In [17]:

heap.heap

heap.heap

Out[17]:

[4, 15, 5, 45]

In [19]:

heap.get_min()

heap.get_min()

Out[19]:

4

In [20]:

heap.delete_key(2)

heap.delete_key(2)

In [21]:

heap.heap

heap.heap

Out[21]:

[4, 15, 45]

In [ ]: