Didn’t understand Heap? Let’s implement and know.

A Sample case of Priority Queue, giving preference to Urgent Businesses.

The Heap Data Structure

Binary Heap is a “Tree Based Data Structure” having a complete “Binary Tree”.

Heaps Can Be classified into two, MIN HEAP and MAX HEAP

MIN HEAP: Both The Left Child and Right Child must be greater than Parents thus min on top whereas in the MAX HEAP : The parent is greater than both the Child, So Maximum goes onto the top

Use Case of Heap, The Priority Queue.

A Heap is useful when there is constant addition and removal of data. Suppose we have a list of elements and we need to draw the highest element in one go but meanwhile, there is a live addition of elements is going on. Let’s understand it with below example.

A case of Call Centre

There is a call centre somewhere, employing half a dozen call attendees, the calls are bursting in, some calls being Basic Issues while a few of them The Real Businesses. How would an Automated System identify and Prioritise this? Here, using a Priority Queue is a feasible option and thus The Heap Data Structure becomes a perfect candidate to recruit. See the below Image for a better understanding.

Calls Will be Prioritised on the based on their Importance

We can Create Heap ourselves, But Python has an Inbuilt Library named “heapq” and to keep the code short, we are using it. If you still want to code Heap for yourself ,You can find a suitable code for yourself from a list of articles available on “geeksforgeeks.org” →Click Here.

So lets Come to the Coding Part to get the essence of it.

Starting Up

#Importing Libraries
import heapq
import time
import random
import schedule
# Adding some calls into the list of tuples
# Priority(1 to 5), ‘Caller name’)
call_queue = [
 (3, ‘c1’),
 (1, ‘c4’),
 (4, ‘c3’),
 (5, ‘c2’),
 (2, ‘c5’),
 ]
# heapify function makes a heap of the given list
heapq.heapify(call_queue)

Adding Functions

Random Call Addition : Since we are creating an example, I am Adding extra Random calls in Queue by scheduling for certain time.

def add_call():
    # With some Random Priorities and Random users
    call_tuple = (
              random.randint(1,5), 
              random.choice(['c13','c15','c17','c18','c11','c14',]))
              
    print('New Incoming call in queue, Caller: ',call_tuple[1],
          '| Priority :',call_tuple[0])
    
    heapq.heappush(call_queue,call_tuple)

Popping out “Next Priority” Call

def call_manager(): 
if len(call_queue)==0:
     return
 else:
     popped = heapq.heappop(call_queue)
     print(‘Call Started for: ‘,popped[1],’ Priority: ‘,popped[0])

Scheduling the Jobs and Running the Schedule

# Scheduling Sample Calls
schedule.every(3).seconds.do(call_manager)
schedule.every(10).seconds.do(add_call)
# Running the Schedule
while True:
    schedule.run_pending() 
    time.sleep(1)

Output : Lets See what is Happening in the Terminal

Whenever be a “High Priority Call” is Added, It is getting “First Priority”

This was an Example of Priority Queue Based on Min Heap. There can be other uses like Finding Min, Max or Median from a list which is constantly appending new elements, Finding a time period with maximum Active Covid cases. Finding the day with minimum or maximum Population.

In Next Blog for Heap, I will create an example for above Call Centre case most probably as an App.

Hope you enjoyed this Piece.

Please like and follow.

Good Bye !!!!! Have a Nice Day