Priority Queue (heap)

Posted on Posted in Creative Problem Solving

Most of people would say, Heap data structures is learnt mainly for heapsort.  They ignore an important point about Heap and it’s enormous set of practical applications.  Let’s take a look at following scenario.

We book an OLA cab at 7:00 PM using Mobile Application for Airport Drop @ 4:00 AM next morning.
OLA informs that they’ll be sent driver and cab details 15 minutes before our journey.  After we’ve booked a cab, many more people would be booking the cabs for ride now or ride later.

Ever wondered, What’s the right data structure to store booking details, so that following operations are most efficient.
1. Picking the next customer who has booking – To send them details of driver and cab.
2. Cancelling the booking – To remove an order from the list.
3. Updating the booking  – To reschedule the booking.
4. Adding a new booking – To add new booking requests for processing.

Possible Solutions

1.  Unsorted Array

We can store the bookings in an unsorted array.  Let’s see the complexity of this solution.

  1.  Insertion: O(1)
  2. Next Customer to Process: O(n)
  3.  Deletion: O(n)
  4.  Updation: O(n)

2.  Sorted Array

You would have guessed by now, that we need to store them in sorted order of travel time so that retrieval is faster.

  1.  Insertion: O(n)
  2.  Next Customer to Process: O(1)
  3.  Deletion: O(n)
  4.  Updation: O(lgn)

3.  Linked List

Same performance as that of array

4.  BST or AVL

  1.  Insertion: O(lgn)
  2.  Next Customer to Process: O(lgN)
  3.  Deletion: O(lgn)
  4.  Updation: O(lgn)

5.  HEAP

Heap solves the problem by providing following compexities

  1.  Insertion: O(lgn)
  2.  Next Customer to Process: O(1)
  3.  Deletion: O(lgn)
  4.  Updation: O(lgn)