Heap Python

Setup

To use heap, we need heapq

from heapq import *

Min Heap

The first way is we can use heapify function which will generate a heap from an array.

• Note: this will modify the original array, which is consider bad, because what if we want to re-use the array after

def minHeap(arr: List[int]):
    heapify(arr)  # BAD: this will modify the arr
    return heappop(arr)

Another way is to push all the item into another heap as it using heappush. This one will create a new array instead of modify the current one

def minHeap(arr: List[int]):
    heap = []
    for num in arr:
        heappush(heap, num)
    return heappop(heap)

Max Heap

Since in heapq, the value is sorted based on the smallest. Therefore to find the max heap, we have to revert the sign of the number

def maxHeap(arr: List[int]):
    heap = []
    for num in arr:
        # push negative since heap pop always return the smallest
        heappush(heap, -num)

    return -heappop(heap)