priority queues and heaps priority queue is basically type of queue that will always return items in order of priority this priority could befor examplethat the lowest item is always popped off first although it is called queuepriority queues are often implemented using heapsince it is very efficient for this purpose consider thatin storecustomers queue in line where service is only rendered at the front of the queue each customer will spend some time in the queue to get served if the waiting times for the customers in the queue are and then the average time spent in the queue becomes ( )/ which is howeverif we change the order of service such that customers with the least amount of waiting time are served firstthen we obtain different average waiting time in doing sowe calculate our new average waiting time by ( )/ which now equals better average waiting time clearlythere is merit to serving the customers from the least waiting time upward this method of selecting the next item by priority or some other criterion is the basis for creating priority queues heap is data structure that satisfies the heap property the heap property states that there must be certain relationship between parent node and its child nodes this property must apply through the entire heap in min heapthe relationship between parent and children is that the parent must always be less than or equal to its children as consequence of thisthe lowest element in the heap must be the root node in max heapon the other handthe parent is greater than or equal to its child or its children it follows from this that the largest value makes up the root node as you can see from what we just mentionedheaps are trees andto be more specificbinary trees although we are going to use binary treewe will actually use list to represent it this is possible because the heap will store complete binary tree complete binary tree is one in which each row must be fully filled before starting to fill the next row