General Idea Example:Suppose there are a sequence of jobs are sent to a printer.Although jobs sent to a printer are generally placed on a queue,this might not always be the best thing to do. For instance,if,when the printer becomes available, there are several 1-page jobs and one 100-page job, it might be reasonable to make the long job go last, even if it is not the last job submitted. This particular application seems to require a special kind of queue,known as a priority queue
General Idea ◼ Example: Suppose there are a sequence of jobs are sent to a printer. Although jobs sent to a printer are generally placed on a queue, this might not always be the best thing to do. ◼ For instance, if, when the printer becomes available, there are several 1-page jobs and one 100-page job, it might be reasonable to make the long job go last, even if it is not the last job submitted. ◼ This particular application seems to require a special kind of queue, known as a priority queue
Model A priority gueue is a data structure that allows at least the following two operations: (1)Insert:is the equivalent of Engueue (2)DeleteMin:finds,returns,and removes the minimum element in the priority queue. DeleteMin(H) Insert(H) Priority Queue H
Model ◼ A priority queue is a data structure that allows at least the following two operations: ◼ (1) Insert: is the equivalent of Enqueue ◼ (2) DeleteMin: finds, returns, and removes the minimum element in the priority queue. Priority Queue H DeleteMin(H) Insert(H)
Simple Implementations There are several obvious ways to implement a priority queue.We could use a simple linked list performing insertions at the front and traversing the list to delete the minimum. Alternatively,we could insist that the list be kept always sorted. Another way of implementing priority queues would be to use a binary search tree.Recall that the only element we ever delete is the minimum.Repeatedly removing a node that is in the left subtree would seem to hurt the balance of the tree by making the right subtree heavy
Simple Implementations ◼ There are several obvious ways to implement a priority queue. We could use a simple linked list, performing insertions at the front and traversing the list to delete the minimum. ◼ Alternatively, we could insist that the list be kept always sorted. ◼ Another way of implementing priority queues would be to use a binary search tree. Recall that the only element we ever delete is the minimum. Repeatedly removing a node that is in the left subtree would seem to hurt the balance of the tree by making the right subtree heavy
Binary Heap The implementation we will use is known as a binary heap. Like binary search trees,binary heaps have two properties,namely,a structure property and a heap order property
Binary Heap ◼ The implementation we will use is known as a binary heap. ◼ Like binary search trees, binary heaps have two properties, namely, a structure property and a heap order property
Structure Property Structure property:A heap is a binary tree that is completely filled,with the possible exception of the bottom level,which is filled from left to right.Such a tree is known as a complete binary tree. B E
Structure Property ◼ Structure property: A heap is a binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree. D E B C A F G H I J