Priority Queue implementation in Python

Priority Queue is an extension of Queue with following properties

• each item has a priority associated with it
• the item with high priority is dequeued before other item with low priority

Binary heap is generally preferred implementation for Priority Queue. It takes time O(log n) to re-heapify the remaining items if the min/max item is removed.The same amount of time O(log n) is taken to insert an new item in the heap.

The key functions to implement in Priority Queue include:

• insert(val)
• extractMin()/extractMax()
• remove(i)
• getMin()/getMax()
• changePriority(i, val)

Implementation in Python:

def left_child(k):
    return 2 * k + 1


def right_child(k):
    return 2 * k + 2


def is_leaf(k):
    return 2 * k >= len(mylist)


def parent(k):
    return (k - 1) // 2


def getMin():
    return mylist[0]


def heapify(k):
    if is_leaf(k):
        return

    n = len(mylist)

    # get left and right child index
    left = left_child(k)
    right = right_child(k)

    # find the smallest elements among current node, its left child and right child if exists
    smallest = k
    if left < n and mylist[k] > mylist[left]:
        smallest = left
    if right < n and mylist[smallest] > mylist[right]:
        smallest = right

    # swap current node and the smallest child
    if smallest != k:
        mylist[k], mylist[smallest] = mylist[smallest], mylist[k]
        heapify(smallest)


def shift_up(i):
    while i > 0 and mylist[i] < mylist[parent(i)]:
        mylist[i], mylist[parent(i)] = mylist[parent(i)], mylist[i]
        i = parent(i)


def insert(val):
    mylist.append(val)
    shift_up(len(mylist) - 1)


def extractMin():
    min = mylist[0]
    mylist[0] = mylist[len(mylist) - 1]
    mylist.pop(len(mylist) - 1)
    heapify(0)
    return min


def remove(i):
    mylist[i] = getMin() - 1
    shift_up(i)
    extractMin()


def print_heap():
    for i in range(len(mylist) // 2):
        left = 2 * i + 1
        right = 2 * i + 2
        if left < len(mylist) and right < len(mylist):
            print(
                f"parent: {mylist[i]} left-child: {mylist[left]} right-child: {mylist[right]}"
            )
        elif left < len(mylist):
            print(f"parent: {mylist[i]} left-child: {mylist[left]} right-child: None")
            
mylist = []            

Build the binary heap:

insert(6)
insert(4)
insert(8)
insert(2)
insert(9)
insert(7)
print(mylist)

Output:
[2,4,7,6,9,8]


         4        4         2         2          2
4  -->  /   -->  / \  -->  / \  -->  / \  -->  /    \ 
       6        6   8     4   8     4   8     4     7
                         /         / \       / \   /
                        6         6   9     6   9 8

Insert a new item:

insert(1)
print(mylist)

Output:
[1,4,2,6,9,8,7]

      2             2             1
    /   \         /   \         /   \
   4     7  -->  4     1  -->  4     2
  / \   / \     / \   / \     / \   / \
 6   9 8   1   6   9 8   7   6   9 8   7

Extract the min item:

extractMin()
print(mylist)

Output:
[2,4,7,6,9,8]

      1             7             2
    /   \         /   \         /   \
   4     2  -->  4     2  -->  4     7
  / \   / \     / \   /       / \   / 
 6   9 8   7   6   9  8      6   9 8

Remove the item at specified position:

remove(1)
print(mylist)

Output:
[2,6,7,8,9]

       2                1(2-1)         8              2              2
     /   \            /   \          /   \          /   \          /   \
    4     7  -->     2     7  -->   2     7  -->   8     7  -->   6     7
   / \   /          / \   /        / \            / \            / \
  6   9 8          6   9 8        6   9          6   9          8   9