priority queues (heapsdeletemin priority queue insert figure basic model of priority queue as with most data structuresit is sometimes possible to add other operationsbut these are extensions and not part of the basic model depicted in figure priority queues have many applications besides operating systems in we will see how priority queues are used for external sorting priority queues are also important in the implementation of greedy algorithmswhich operate by repeatedly finding minimumwe will see specific examples in and in this we will see use of priority queues in discrete event simulation simple implementations there are several obvious ways to implement priority queue we could use simple linked listperforming insertions at the front in ( and traversing the listwhich requires (ntimeto delete the minimum alternativelywe could insist that the list be kept always sortedthis makes insertions expensive ( ( )and deletemins cheap ( ( )the former is probably the better idea of the twobased on the fact that there are never more deletemins than insertions another way of implementing priority queues would be to use binary search tree this gives an (log naverage running time for both operations this is true in spite of the fact that although the insertions are randomthe deletions are not recall that the only element we ever delete is the minimum repeatedly removing node that is in the left subtree would seem to hurt the balance of the tree by making the right subtree heavy howeverthe right subtree is random in the worst casewhere the deletemins have depleted the left subtreethe right subtree would have at most twice as many elements as it should this adds only small constant to its expected depth notice that the bound can be made into worst-case bound by using balanced treethis protects one against bad insertion sequences using search tree could be overkill because it supports host of operations that are not required the basic data structure we will use will not require links and will support both operations in (log nworst-case time insertion will actually take constant time on averageand our implementation will allow building priority queue of items in linear timeif no deletions intervene we will then discuss how to implement priority queues to support efficient merging this additional operation seems to complicate matters bit and apparently requires the use of linked structure