pq and min heap Link to heading

The following is some implementation of priority queue in python In python, the default order is ascending, so it’s also a min-heap

from heapq import heappop, heappush, nlargest, nsmallest
from typing import Any


class PriorityQueue:
    """PriortyQuque implementation."""
    def __init__(self) -> None:
        self.pq = []

    def peek(self) -> Any:
        if self.pq: return self.pq[0]
        return None

    def pop(self) -> Any:
        if self.pq: return heappop(self.pq)
        return None

    def push(self, obj: Any) -> None:
        heappush(self.pq, obj)


if __name__ == "__main__":
    pq = PriorityQueue()
    pq.push(3)
    pq.push(5)
    pq.push(-1)
    pq.push(0)

    assert (nlargest(3, pq.pq) == [5, 3, 0])
    assert (nsmallest(3, pq.pq) == [-1, 0, 3])

# time complexity:
# push -- heappush O(logn)
# pop -- heappop O(logn)
# peek -- random access iterable 0 O(1)

P.S: All the interesting methods are in Lib/heapq.py

max heap Link to heading

Now let’s see how to implement a max heap.

from heapq import heappop, heappush, nlargest, nsmallest
from typing import Any


class MaxHeapInt:
    """Max heap object."""
    def __init__(self, val: int) -> None:
        self.val = val

    def __lt__(self, other: "MaxHeapInt") -> bool:
        return self.val > other.val

    def __eq__(self, other: "MaxHeapInt") -> bool:
        return self.val == other.val


class MaxHeap:
    """Max heap implementation."""
    def __init__(self) -> None:
        self.pq = []

    def peek(self) -> Any:
        if self.pq: return self.pq[0]
        return None

    def pop(self) -> Any:
        if self.pq: return heappop(self.pq)
        return None

    def push(self, obj: Any) -> None:
        heappush(self.pq, obj)


if __name__ == "__main__":
    pq = MaxHeap()
    pq.push(MaxHeapInt(3))
    pq.push(MaxHeapInt(5))
    pq.push(MaxHeapInt(-1))
    pq.push(MaxHeapInt(0))

    assert ([i.val for i in nlargest(3, pq.pq)] == [-1, 0, 3])
    assert ([i.val for i in nsmallest(3, pq.pq)] == [5, 3, 0])

# time complexity:
# push -- heappush O(logn)
# pop -- heappop O(logn)
# peek -- random access iterable 0 O(1)

Another way forming a “max heap” is to use -1*element to represent element in the heap.

heapify Link to heading

heapify can take linear time transform a list into a MIN heap (in python min heap is the default). It seems like pretty difficult to write comparitors like __lt__ in other functions to customize heapify, because heapify uses cmp_lt a customized comparitor to do comparison.