priority queues (heapsif the event is an arrivalwe check for an available teller if there is nonewe place the arrival on the line (queue)otherwise we give the customer tellercompute the customer' departure timeand add the departure to the set of events waiting to happen the waiting line for customers can be implemented as queue since we need to find the event nearest in the futureit is appropriate that the set of departures waiting to happen be organized in priority queue the next event is thus the next arrival or next departure (whichever is sooner)both are easily available it is then straightforwardalthough possibly time-consumingto write the simulation routines if there are customers (and thus eventsand tellersthen the running time of the simulation would be ( log( )because computing and processing each event takes (log )where is the size of the heap -heaps binary heaps are so simple that they are almost always used when priority queues are needed simple generalization is -heapwhich is exactly like binary heap except that all nodes have children (thusa binary heap is -heapfigure shows -heap notice that -heap is much shallower than binary heapimproving the running time of inserts to (logd nhoweverfor large dthe deletemin operation is more expensivebecause even though the tree is shallowerthe minimum of children must be foundwhich takes comparisons using standard algorithm this raises the time for this operation to ( logd nif is constantboth running times areof courseo(log nalthough an array can still be usedthe multiplications and divisions to find children and parents are now by dwhichunless is power of seriously increases the running timebecause we can no longer implement division by bit shift -heaps are interesting in theorybecause there are many algorithms where the number of insertions is much greater than the number of deletemins (and thus theoretical speedup is possiblethey are also of interest when the priority queue is too large to fit entirely in main memory figure -heap ( we use ( log( )instead of ( log kto avoid confusion for the case