4. Max Heap

Max 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

In [9]:

class MaxHeap:
    def __init__(self, arr):
        self.heap = arr
        self.size = len(self.heap)

    def max_heapify(self, i):
        largest = i

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

        # check whether the left child index is within array bounds
        # check if the current element is smaller than the left child
        # if yes then set left child index to be the largest
        if left_child_idx < self.size and self.heap[i] < self.heap[left_child_idx]:
            largest = left_child_idx

        # check whether the right child index is within array bounds
        # check if the current element is smaller than the left child
        # if yes then set left child index to be the largest
        if (
            right_child_idx < self.size
            and self.heap[largest] < self.heap[right_child_idx]
        ):
            largest = right_child_idx

        # if one of the above has set largest then we need to swap the largest element
        # with the current node we are looking at
        # and then continue doing heapify until the largest element
        # is pushed in the correct place
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.max_heapify(largest)

    def build_max_heap(self):

        n = int((len(self.heap) // 2) - 1)
        for k in range(n, -1, -1):
            self.max_heapify(k)

    def delete(self, num):
        for i in range(self.size):
            if num == i:
                break

        self.heap[i], self.heap[self.size - 1] = self.heap[self.size - 1], self.heap[i]
        self.heap.remove(num)
        self.size -= 1
        for i in range((self.size // 2) - 1, -1, -1):
            self.max_heapify(i)

    def print_heap(self):
        pass

    def get_max(self):
        if self.size > 0:
            return self.heap[0]

class MaxHeap: def __init__(self, arr): self.heap = arr self.size = len(self.heap) def max_heapify(self, i): largest = i left_child_idx = 2 * i + 1 right_child_idx = 2 * i + 2 # check whether the left child index is within array bounds # check if the current element is smaller than the left child # if yes then set left child index to be the largest if left_child_idx < self.size and self.heap[i] < self.heap[left_child_idx]: largest = left_child_idx # check whether the right child index is within array bounds # check if the current element is smaller than the left child # if yes then set left child index to be the largest if ( right_child_idx < self.size and self.heap[largest] < self.heap[right_child_idx] ): largest = right_child_idx # if one of the above has set largest then we need to swap the largest element # with the current node we are looking at # and then continue doing heapify until the largest element # is pushed in the correct place if largest != i: self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i] self.max_heapify(largest) def build_max_heap(self): n = int((len(self.heap) // 2) - 1) for k in range(n, -1, -1): self.max_heapify(k) def delete(self, num): for i in range(self.size): if num == i: break self.heap[i], self.heap[self.size - 1] = self.heap[self.size - 1], self.heap[i] self.heap.remove(num) self.size -= 1 for i in range((self.size // 2) - 1, -1, -1): self.max_heapify(i) def print_heap(self): pass def get_max(self): if self.size > 0: return self.heap[0]

In [10]:

arr = list(range(10))
heap = MaxHeap(arr)

heap.build_max_heap()

arr = list(range(10)) heap = MaxHeap(arr) heap.build_max_heap()

In [11]:

heap.heap

heap.heap

Out[11]:

[9, 8, 6, 7, 4, 5, 2, 0, 3, 1]

In [12]:

heap.delete(9)

heap.delete(9)

In [13]:

heap.heap

heap.heap

Out[13]:

[8, 6, 7, 4, 5, 2, 0, 3, 1]

In [14]:

heap.delete(5)

heap.delete(5)

In [15]:

heap.heap

heap.heap

Out[15]:

[8, 6, 7, 4, 1, 0, 3, 2]

In [16]:

import heapq

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

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

[8, 6, 7, 4, 1, 0, 3, 2]

In [17]:

heap.get_max()

heap.get_max()

Out[17]:

8

In [ ]: