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.

• Step1: Append the inserted val in the end of heap array.
• Step2: heaplify up till right position.

2. Delete

• Step1: Swap the first value with end value in the heap array
• Step2: heaplify down till right position.
• Step3: pop the last element in the heap array.

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