Design and Analysis of
Algorithms
Instructor: Miss.Roaa Solh
Title: Priority Queue
By:Khaled Dahrouj
Mahmoud Dafer
Moe Mehyedine
COSC 216
Priority Queues:
Definition: a priority queue is an abstract data type which is like a
regular queue or stack data structure, but where additionally each element
has a "priority" associated with it. In a priority queue, an element with
high priority is served before an element with low priority.
A typical priority queue supports following operations:
Recall stacks and queues (common abstract data types)
Priority queue is similar (print jobs, work requests)
Queues use FIFO – here we retrieve elements according to their
priority (low is high)
Insert – any order
Remove – highest priority (take minimum element)
Code example:
PriorityQueue<Job> q = new PriorityQueue<Job>();
q.add(new Job(5, “Clean pool”));
q.add(new Job(3, “Clean windows”));
q.add(new Job(3, “Clean carpets”));
q.add(new Job(1, “Clean self”));
Removes in order self, windows, carpets, pool (q.remove())
Note that priority numbers determine order of removal
Implementation:
Could use a linked list (elements are Jobs)
Add new elements to list at front
Remove elements according to priority
Add would be fast
Remove would be slow
Could use a BinarySearchTree – easy to locate elements for add,
remove but the tree might require major rearrangement
Heaps – most elegant structure invented.
Heap is a binary tree with two properties:
A heap is almost complete – all nodes are filled in except the
last level may have some missing towards the right.
The tree has the heap property – all nodes store values that are
at most as large as the values stored in their descendants.
The heap property => smallest element is at the root.
Binary Search Trees are very similar but they can have arbitrary
shape.
In a heap the left and right subtrees both store elements that are
larger than the root (not smaller and larger – as per BST).
Examples of Min Heap:
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
How is Binary Heap represented?
A Binary Heap is a Complete Binary Tree. A binary heap is typically
represented as an array.
The root element will be at Arr[0].
Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[(i-1)/2] Returns the parent node
Arr[(2*i)+1] Returns the left child node
Arr[(2*i)+2] Returns the right child node
Array Implementation:
Very efficient
No inner class of nodes needed – no links needed for children
Use index and child index computations
Advantages and Disadvantages
1) Advantages:
Consider the following array:
[0] [1] [2] [3] [4] [5] [6] [7] [8] …
20 75 43 84 90 57 71 93 …
Store the levels of the tree from left to right in an array
Indices of children are easy to find – for index i the children are at 2i
and 2i + 1
2) Disadvantages:
Disadvantage: May be slower than optimal and may use lots of space
to store all N records for huge N.
