Priority Queue under the hood implemented using python

This article is to make sure when you use heap library in the real interview, the interviewer ask you details about it, you won’t fail.

PQ is implemented using binary heap tree.

Binary heap tree is

  1. It’s a complete binary tree.
  2. Could be max heap or min heap. The parent and child follow the relationship in figure.
  3. the tree is represented by array.
parent-child relationship

There’re mainly two methods:

1.Insert using heaplify up.

2. Delete

Both take O(log n) running time.

helper function

Reference:

1.article:https://medium.com/@tobby168/%E7%94%A8-python-%E5%AF%A6%E4%BD%9C-binary-heaps-priority-queue-12e0b82ed7b3
2.video:https://www.youtube.com/watch?v=WYAUQO7hk4I&ab_channel=AhsanKamal