3. Binary Heap implementation using Python List

Binary Heaps¶

References:¶

1. https://www.programiz.com/dsa/heap-data-structure
2. https://favtutor.com/blogs/heap-in-python
3. https://www.codesdope.com/blog/article/priority-queue-using-heap/
4. https://runestone.academy/ns/books/published/pythonds/Trees/BinaryHeapImplementation.html

In [7]:

class Heap:
    def __init__(self, arr=None):
        self.heap = []
        self.heap_size = 0
        if arr is not None:
            self.heap = arr
            self.heap_size = len(self.heap)

    def min_heapify(self, parent):
        smallest = parent
        left_child = 2 * parent + 1
        right_child = 2 * parent + 2

        if left_child < self.heap_size and self.heap[parent] > self.heap[left_child]:
            smallest = left_child
        if (
            right_child < self.heap_size
            and self.heap[smallest] > self.heap[right_child]
        ):
            smallest = right_child

        if smallest != parent:
            self.swap(smallest, parent)
            # heapify again the one which has been moved
            self.min_heapify(smallest)

    def insert_max_heap(self, key):
        self.heap.append(key)
        self.heap_size += 1
        n = (self.heap_size // 2) - 1
        for node in range(n, -1, -1):
            self.max_heapify(node)

    def insert_min_heap(self, key):
        self.heap.append(key)
        self.heap_size += 1
        n = (self.heap_size // 2) - 1
        for node in range(n, -1, -1):
            self.min_heapify(node)

    def max_heapify(self, parent):
        largest = parent

        left_child = 2 * parent + 1
        right_child = 2 * parent + 2

        if left_child < self.heap_size and self.heap[parent] < self.heap[left_child]:
            largest = left_child

        if right_child < self.heap_size and self.heap[largest] < self.heap[right_child]:
            largest = right_child

        if largest != parent:
            # self.swap(largest, parent)
            self.heap[largest], self.heap[parent] = (
                self.heap[parent],
                self.heap[largest],
            )
            self.max_heapify(largest)

    def swap(self, idx_a, idx_b):
        self.heap[idx_a], self.heap[idx_b] = (self.heap[idx_b], self.heap[idx_a])

    def build_min_heap(self):
        n = (self.heap_size // 2) - 1
        for node in range(n, -1, -1):
            self.min_heapify(node)

    def build_max_heap(self):
        n = (self.heap_size // 2) - 1
        # loop only goes up to the half due to complete binary tree property
        # leaves are found half way
        for node in range(n, -1, -1):
            self.max_heapify(node)

    def print_root(self):
        print(self.heap[0])

    def get_max_root_method_1(self):
        if self.heap_size > 0:
            element = self.heap.pop(0)
            self.heap_size -= 1
            self.max_heapify(0)
            return element
        else:
            print("Heap is empty")

    def get_max_root_method_2(self):
        if self.heap_size > 0:
            element = self.heap[0]
            self.heap[0] = self.heap[self.heap_size - 1]
            del self.heap[self.heap_size - 1]
            self.heap_size -= 1
            self.max_heapify(0)
            return element
        else:
            print("Heap is empty")

    def get_min_root(self):
        if self.heap_size > 0:
            element = self.heap.pop(0)
            self.heap_size -= 1
            self.min_heapify(0)
            return element
        else:
            print("Heap is empty")

class Heap: def __init__(self, arr=None): self.heap = [] self.heap_size = 0 if arr is not None: self.heap = arr self.heap_size = len(self.heap) def min_heapify(self, parent): smallest = parent left_child = 2 * parent + 1 right_child = 2 * parent + 2 if left_child < self.heap_size and self.heap[parent] > self.heap[left_child]: smallest = left_child if ( right_child < self.heap_size and self.heap[smallest] > self.heap[right_child] ): smallest = right_child if smallest != parent: self.swap(smallest, parent) # heapify again the one which has been moved self.min_heapify(smallest) def insert_max_heap(self, key): self.heap.append(key) self.heap_size += 1 n = (self.heap_size // 2) - 1 for node in range(n, -1, -1): self.max_heapify(node) def insert_min_heap(self, key): self.heap.append(key) self.heap_size += 1 n = (self.heap_size // 2) - 1 for node in range(n, -1, -1): self.min_heapify(node) def max_heapify(self, parent): largest = parent left_child = 2 * parent + 1 right_child = 2 * parent + 2 if left_child < self.heap_size and self.heap[parent] < self.heap[left_child]: largest = left_child if right_child < self.heap_size and self.heap[largest] < self.heap[right_child]: largest = right_child if largest != parent: # self.swap(largest, parent) self.heap[largest], self.heap[parent] = ( self.heap[parent], self.heap[largest], ) self.max_heapify(largest) def swap(self, idx_a, idx_b): self.heap[idx_a], self.heap[idx_b] = (self.heap[idx_b], self.heap[idx_a]) def build_min_heap(self): n = (self.heap_size // 2) - 1 for node in range(n, -1, -1): self.min_heapify(node) def build_max_heap(self): n = (self.heap_size // 2) - 1 # loop only goes up to the half due to complete binary tree property # leaves are found half way for node in range(n, -1, -1): self.max_heapify(node) def print_root(self): print(self.heap[0]) def get_max_root_method_1(self): if self.heap_size > 0: element = self.heap.pop(0) self.heap_size -= 1 self.max_heapify(0) return element else: print("Heap is empty") def get_max_root_method_2(self): if self.heap_size > 0: element = self.heap[0] self.heap[0] = self.heap[self.heap_size - 1] del self.heap[self.heap_size - 1] self.heap_size -= 1 self.max_heapify(0) return element else: print("Heap is empty") def get_min_root(self): if self.heap_size > 0: element = self.heap.pop(0) self.heap_size -= 1 self.min_heapify(0) return element else: print("Heap is empty")

In [8]:

arr = [3, 9, 2, 1, 4, 5]
min_heap = Heap(arr)
min_heap.build_min_heap()
print(min_heap.heap)
min_heap.print_root()
print(min_heap.get_min_root())
print(min_heap.heap)

arr = [3, 9, 2, 1, 4, 5] min_heap = Heap(arr) min_heap.build_min_heap() print(min_heap.heap) min_heap.print_root() print(min_heap.get_min_root()) print(min_heap.heap)

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

In [9]:

min_heap.insert_min_heap(1)
print(min_heap.heap)

min_heap.insert_min_heap(1) print(min_heap.heap)

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

In [10]:

for i in range(min_heap.heap_size):
    print(min_heap.get_min_root())

for i in range(min_heap.heap_size): print(min_heap.get_min_root())

1
2
3
4
5
9

In [11]:

arr = [3, 9, 2, 1, 4, 5]
max_heap = Heap(arr)
max_heap.build_max_heap()
print(max_heap.heap)
max_heap.print_root()
print(max_heap.get_max_root_method_1())
print(max_heap.heap)

arr = [3, 9, 2, 1, 4, 5] max_heap = Heap(arr) max_heap.build_max_heap() print(max_heap.heap) max_heap.print_root() print(max_heap.get_max_root_method_1()) print(max_heap.heap)

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

In [12]:

max_heap.insert_max_heap(9)
print(max_heap.heap)

max_heap.insert_max_heap(9) print(max_heap.heap)

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

In [13]:

for i in range(max_heap.heap_size):
    print(max_heap.get_max_root_method_1())

for i in range(max_heap.heap_size): print(max_heap.get_max_root_method_1())

9
5
4
3
2
1

In [14]:

arr = [3, 9, 2, 1, 4, 5]
max_heap = Heap(arr)
max_heap.build_max_heap()
print(max_heap.heap)
max_heap.print_root()
print(max_heap.get_max_root_method_2())
print(max_heap.heap)

arr = [3, 9, 2, 1, 4, 5] max_heap = Heap(arr) max_heap.build_max_heap() print(max_heap.heap) max_heap.print_root() print(max_heap.get_max_root_method_2()) print(max_heap.heap)

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

In [15]:

max_heap.insert_max_heap(9)
print(max_heap.heap)

max_heap.insert_max_heap(9) print(max_heap.heap)

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

In [16]:

for i in range(max_heap.heap_size):
    print(max_heap.get_max_root_method_2())

for i in range(max_heap.heap_size): print(max_heap.get_max_root_method_2())

9
5
4
3
2
1

In [ ]: