Review of Priority Queues and Graphs
David Weir (U of Sussex) Program Analysis Term 1, 2015 80 / 192
Priority Queue Abstract Datatype
What does a priority queue look like? An ordered sequence of elements
(a1,…,an)
A linear data structure
a1 is the first element in the queue an is the last element in the queue
David Weir (U of Sussex) Program Analysis Term 1, 2015 81 / 192
Priorities
What role do priorities play?
Ordering of elements is determined by the priority associated with each element
a1 has as high a priority as any element in a1,…,an Priorities do not need to be distinct
— provide a partial ordering of elements in the queue Priorities can change as a computation proceeds
David Weir (U of Sussex) Program Analysis Term 1, 2015 82 / 192
Issues
How might priorities be determined?
What operations are typically performed on priority queues? How can priority queues be efficiently implemented?
David Weir (U of Sussex) Program Analysis Term 1, 2015 83 / 192
Priorities
A queue of jobs to be processed by some resource — priority determined by importance/urgency of job
A queue of items on an agenda
— priority measures whether items are ready to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2015 84 / 192
Priority Queue Operations
Find/remove element with highest priority on queue
Add new element to queue
Update priority of element on queue
Determine if queue is empty (or more generally length of queue) Return an empty priority queue
David Weir (U of Sussex) Program Analysis Term 1, 2015 85 / 192
Implementations of Priority Queues
We will consider two alternatives: Unsorted list implementation Heap implementation
David Weir (U of Sussex) Program Analysis Term 1, 2015 86 / 192
Unsorted List Implementation
Elements arranged in arbitrary order
— e.g. the order in which they were added
Example:
a1
a2
a3
a4
a5
a6
a7
a8
lowest priority element
highest priority element
last element added
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
87 / 192
Efficiency of Unsorted List Implementation
Suppose we have a queue containing n elements: (a1, . . . , an) Adding new element:
— add to end of list
— takes Θ(1) time to execute
Removing front of queue:
— requires linear search of queue
— takes O(n) time in worst-case, O(1) in best-case Update priority of an element:
— no reordering of elements required
— takes Θ(1) assuming constant time access to priority values
David Weir (U of Sussex) Program Analysis Term 1, 2015 88 / 192
Heap Implementation
What is a heap?
An array of values where ordering is constrained in a particular way
A full binary tree
a1
a2
a3
a4
a5
a6
a7
a8
root of
tree left child
of root
right child of root
rightmost grandchild of root
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
89 / 192
Heaps
In general:
a1
…
ai
…
a2i
a2i +1
…
an
root of some node tree within tree
left child of ai
right child of ai
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 90 / 192
Heap as Tree
a1
a3
a4 a5 a6 a7
a8 a9 a10 a11 a12 a13 a14
a2
a15
David Weir (U of Sussex) Program Analysis Term 1, 2015
91 / 192
Heap Ordering
The clever idea behind heaps:
Exploits a “light-touch” ordering scheme
Goal: just ordered enough to be useful
— the highest priority element can be found quickly
— avoid unnecessarily maintaining complete orderliness
A heap is well-formed when for each i the priority of ai is as high as the priority of its children
For all i:
priority (ai ) ≥ priority (a2i ) priority(ai) ≥ priority(a2i+1)
David Weir (U of Sussex) Program Analysis Term 1, 2015 92 / 192
Example Heap
98
97
14 88 15 10
10 13 70 1 12 13 3 2
20
98
97
20
14
88
15
10
10
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
David Weir (U of Sussex) Program Analysis Term 1, 2015 93 / 192
Working with Heaps
How do we add an element to a heap?
Insert new element to end of sequence Repeatedly swap with parent if higher priority This is operation is called heapify
David Weir (U of Sussex) Program Analysis Term 1, 2015 94 / 192
Adding a New Element
98
97
14 88 15 10
10 13 70 1 12 13 3 2
50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 95 / 192
20
98
97
20
14
88
15
10
10
13
70
1
12
13
3
2
50
Exchange with Parent
98
97
14 88 15 10
50 13 70 1 12 13 3 2 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 96 / 192
20
98
97
20
14
88
15
10
50
13
70
1
12
13
3
2
10
Exchange with Parent
98
97
50 88 15 10
14 13 70 1 12 13 3 2 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 97 / 192
20
98
97
20
50
88
15
10
14
13
70
1
12
13
3
2
10
Running Time
How long does it take to insert an element into a heap?
The number of exchanges is bounded by the depth of the tree The tree is a balanced binary tree so has depth log n
The running time is O(log n) in worst-case
Best-case running time is O(1)
David Weir (U of Sussex) Program Analysis Term 1, 2015 98 / 192
Removing Element from Heap
Not quite as easy as it sounds
The highest priority element is at the front of the sequence Need to restore heap property
Insert last element in sequence at front and put down tree as required
David Weir (U of Sussex) Program Analysis Term 1, 2015 99 / 192
Illustrative Example
98
97
50 88 15 10
14 13 70 1 12 13 3 2 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 100 / 192
20
98
97
20
50
88
15
10
14
13
70
1
12
13
3
2
10
Remove Root
97 20
50 88 15 10
14 13 70 1 12 13 3 2 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 101 / 192
97
20
50
88
15
10
14
13
70
1
12
13
3
2
10
Insert Last Element at Root
10
97
50 88 15 10
14 13 70 1 12 13 3 2
20
10
97
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 102 / 192
Compare Root with Children
10
97
20
50 88 15 10
14 13 70 1 12 13 3 2
10
97
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 103 / 192
Left Child Should be Root
10
97
20
50 88 15 10
14 13 70 1 12 13 3 2
10
97
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 104 / 192
Swop Root and Left Child
97
10
20
50 88 15 10
14 13 70 1 12 13 3 2
97
10
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 105 / 192
Compare with Children
97
10
50 88 15 10
14 13 70 1 12 13 3 2
20
97
10
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 106 / 192
Right Child Should Move Up
97
10
50 88 15 10
14 13 70 1 12 13 3 2
20
97
10
20
50
88
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 107 / 192
Swop Nodes
97
88
50 10 15 10
14 13 70 1 12 13 3 2
20
97
88
20
50
10
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 108 / 192
Compare with Children
97
88
50 10 15 10
14 13 70 1 12 13 3 2
20
97
88
20
50
10
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 109 / 192
Left Child Should Move Up
97
88
50 10 15 10
14 13 70 1 12 13 3 2
20
97
88
20
50
10
15
10
14
13
70
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 110 / 192
Swop Nodes
97
88
50 70 15 10
14 13 10 1 12 13 3 2
20
97
88
20
50
70
15
10
14
13
10
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 111 / 192
Restored the Heap
97
88
50 70 15 10
14 13 10 1 12 13 3 2
20
97
88
20
50
70
15
10
14
13
10
1
12
13
3
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 112 / 192
A Heap for you to restore
68
90
57
59
75
30
22
43
10
16
20
13
17
2
21
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Show the heap as a tree
David Weir (U of Sussex) Program Analysis Term 1, 2015 113 / 192
A Heap for you to restore
68
90
57
59
75
30
22
43
10
16
20
13
17
2
21
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Show the heap as a tree
90
68
75
57 59 21 30
22 43 10 16 20 13 17 2
David Weir (U of Sussex) Program Analysis Term 1, 2015 113 / 192
Running Time
How Long Does This Take?
Worst-case bounded by depth of tree, so O(log n)
Best-case O(1)
David Weir (U of Sussex) Program Analysis Term 1, 2015 114 / 192
Building a Heap from Scratch
Two approaches:
Straightforward approach:
— repeatedly insert new elements — each insertion takes O(log n) time — total running time is O(n log n)
More efficient alternative: — create heap bottom-up
David Weir (U of Sussex) Program Analysis Term 1, 2015 115 / 192
Bottom-up Heap Construction
Consider nodes in order of increasing height in tree Height of a node is length of longest path to leaf node
Restore heap for subtree rooted at node being considered — through required exchanges with highest priority child
David Weir (U of Sussex) Program Analysis Term 1, 2015 116 / 192
Heapification Order
44
32
37 75 15 29
94 25 48 19 58 72 23 11
65
44
32
65
37
75
15
29
94
25
48
19
58
72
23
11
height 322111100000000
David Weir (U of Sussex) Program Analysis Term 1, 2015 117 / 192
Analysis of Running Time
For each node, processing time for node of height
O(h)
Number of nodes of height h ≤n
2h+1
David Weir (U of Sussex) Program Analysis Term 1, 2015 118 / 192
Total Running Time
⌈logn⌉ n 1 ⌈logn⌉ 1
h=0 2h+1O(h) = 2n h=0 2hO(h)
⌈logn⌉ h = O n h = 0 2 h
= O(n)
note that ∞ h=0 2h
h converges to 2
David Weir (U of Sussex) Program Analysis Term 1, 2015 119 / 192
Review of Graphs
David Weir (U of Sussex) Program Analysis Term 1, 2015 120 / 192
Graphs
A general purpose data structure
Need not be linear like a list, but could be
Need not be hierarchical like a tree, but could be
Can express arbitrary binary relationship between a collection of elements
Strength of relationship can be encoded using weights
David Weir (U of Sussex) Program Analysis Term 1, 2015 121 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
Let’s look at an example graph
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v1
v5
v8
v3 There are 8 vertices or nodes
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v1 v5
v8
v3
Use n to refer to the number of nodes — so n = 8
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1 v5
v3
Use V to refer to the set of all nodes — so V = {v1,…,v8}
v6
David Weir (U of Sussex) Program Analysis Term 1, 2015 122 / 192
Graphs: Examining an Example
v2 v4 v7
v1
v5
v8
v3
v6
There are 10 edges
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
Each edge denoted by a set of two vertices
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
v6
For example: {v5,v7} David Weir (U of Sussex)
Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1 v5
v3 v6 Use m to refer to the number of edges — so m = 10
David Weir (U of Sussex) Program Analysis Term 1, 2015 122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
Use E to refer to the set of all edges
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
E = {{v1, v2}, {v1, v3}, {v2, v3}, {v2, v5}, {v3, v6},
{v4, v6}, {v4, v7}, {v5, v7}, {v5, v8}, {v6, v8}} David Weir (U of Sussex) Program Analysis
v6
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v1
v5
v8
v3
Use G to refer to the graph — so G = (V,E)
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v2 v4 v7
v8
v1
v5
v3
The layout of the graph is unimportant
v6
David Weir (U of Sussex) Program Analysis
Term 1, 2015
122 / 192
Graphs: Examining an Example
v5 v2 v1
v8 v4 v7 v3
v6 This is the same graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 122 / 192
What Are Graphs Good For?
Expressing all sorts of binary relationships
Transport networks
◮ node: a place
◮ edge: route connecting two places
Communication networks
◮ node: computer cluster
◮ edge: communication link between two clusters
David Weir (U of Sussex) Program Analysis Term 1, 2015 123 / 192
What Are Graphs Good For?
Information networks
◮ node: web page
◮ edge: hyperlink from one page to another Social networks
◮ node: person
◮ edge: some sort of relationship between two people
Dependency networks
◮ node: task to be performed
◮ edge: dependency between two tasks And much much more
David Weir (U of Sussex) Program Analysis Term 1, 2015 124 / 192
Directed Graphs
v5 v2 v1
v8 v4 v7 v3
v6
Sometimes relationships are directional
David Weir (U of Sussex) Program Analysis Term 1, 2015 125 / 192
Directed Graphs
v5 v2 v1
v8 v4 v7 v3
v6
Capture this with directional edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 125 / 192
Directed Graphs
v5 v2 v1
v8 v4 v7 v3
v6
This is called a directed graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 125 / 192
Directed Graphs
v5 v2 v1
v8 v4 v7 v3
v6
E is now a set of directed pairs
David Weir (U of Sussex) Program Analysis Term 1, 2015 125 / 192
Directed Graphs
v5 v2 v1
v8 v4 v7 v3
v6
E = {(v1, v2), (v3, v1), (v2, v3), (v2, v5), (v6, v3),
(v4, v6), (v7, v4), (v5, v7), (v8, v5), (v6, v8)}
David Weir (U of Sussex) Program Analysis Term 1, 2015 125 / 192
Directed Acyclic Graphs
v5 v2 v1
v8 v4 v7 v3
v6
Important special case: directed acyclic graphs or DAGs
David Weir (U of Sussex) Program Analysis Term 1, 2015 126 / 192
Weighted Graphs
v5 v2 v1
v8 v4 v7 v3
v6
Sometimes want to associate weights with edges – e.g. distance
David Weir (U of Sussex) Program Analysis Term 1, 2015 127 / 192
Weighted Graphs
v5 v2 v1
v8 v4 v7 v3
v6
Capture this with weighted edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 127 / 192
Weighted Graphs
29
v 8 v 15 v 521
14
2
40
v8 v4 v7 v3 11
6 v6
This is called a weighted graph
41
33
David Weir (U of Sussex) Program Analysis Term 1, 2015 127 / 192
Trees: A Special Kind of Graph
v5 v2 v1
v8 v4 v7 v3
v6
Let’s remove these edges to give a tree
David Weir (U of Sussex) Program Analysis Term 1, 2015 128 / 192
Trees: A Special Kind of Graph
v5 v2 v1
v8 v4 v7 v3
v6
How can we tell that its a tree?
David Weir (U of Sussex) Program Analysis Term 1, 2015 128 / 192
Trees: A Special Kind of Graph
v5 v2 v1
v8 v4 v7 v3
v6 Let’s pick it up by v8
David Weir (U of Sussex) Program Analysis Term 1, 2015 128 / 192
Trees: A Special Kind of Graph
v8
v5
v6
v3
v4
v7 v2 v1 What happens if we put back the edges we removed
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 Adding that one creates a cycle
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 Adding that one also creates a cycle
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 Guess what!
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 Fact 1: there are no cycles
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1
Fact 2: its connected, i.e. path between any pair of nodes
David Weir (U of Sussex) Program Analysis Term 1, 2015 128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 Fact 3: n nodes and n − 1 edges
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Trees: A Special Kind of Graph
v8
v5 v6
v3 v4
v7 v2 v1 . . . and that’s what makes it a tree
David Weir (U of Sussex) Program Analysis
Term 1, 2015
128 / 192
Graphs: Implementation
Question: What data structure can we use to store a graph?
Answer: There are two alternatives: Adjacency matrix
Adjacency list
David Weir (U of Sussex) Program Analysis Term 1, 2015 129 / 192
Adjacency Matrix Representation
Adjacency matrix for undirected graph shown earlier
v1 v2 v3 v4 v5 v6 v7 v8 v1 0 v2 0 v3 0 v4 0 v5 1 v6 1 v7 0 v8 0 0 0 0 1 1 0 0
Entry value in (i,j) same as value in (j,i) for undirected graph
0
1
1
0
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
David Weir (U of Sussex) Program Analysis Term 1, 2015 130 / 192
Adjacency Matrix Representation
Adjacency matrix for directed graph shown earlier
v1 v2 v3 v4 v5 v6 v7 v8 v1 0 v2 0 v3 0 v4 0 v5 0 v6 1 v7 0 v8 0 0 0 0 1 0 0 0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
David Weir (U of Sussex) Program Analysis Term 1, 2015 131 / 192
Adjacency Matrix Representation (cont.)
Two issues worth considering:
Space efficiency of adjacency matrix representation
Running time of basic operations of adjacency matrix representation
David Weir (U of Sussex) Program Analysis Term 1, 2015 132 / 192
Space Efficiency of Adjacency Matrix Representation
Given a graph G = (V,E) where |V| = n and |E| = m Question: How much space used to store G? Answer: Θ(n2)
Doesn’t matter how many edges there are
i.e. its not a function of m
Inefficient for graphs without many edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 133 / 192
Time Efficienty of Matrix Representation
First, the good news:
It takes Θ(1) to determine if there’s an edge between two nodes
The not so good news:
It takes Θ(n) to find all nodes adjacent to some node
Even if there aren’t any adjacent nodes it still takes Θ(n) to discover this
Common for an algorithm to need to enumerate adjacent nodes Desirable that finding next node in enumeration take constant time
David Weir (U of Sussex) Program Analysis Term 1, 2015 134 / 192
Adjacency List Representation
v1 v2 v3 v4 v5 v6 v7 v8
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
135 / 192
v2
v3
v1
v4
v5
v1
v2
v6
v6
v7
v2
v7
v4
v8
v3
v8
v4
v5
v5
v6
Adjacency List Representation Features
Same two issues need to be considered:
Space efficiency of adjacency list representation
Running time of basic operations of adjacency list representation
David Weir (U of Sussex) Program Analysis Term 1, 2015 136 / 192
Space Efficiency of Adjacency List Representation
Given a graph G = (V,E) where |V| = n and |E| = m
Question: How much space used to store G?
Answer: Θ(m)
More efficient than adjacency matrix for graphs without many edges
David Weir (U of Sussex) Program Analysis Term 1, 2015 137 / 192
Time Efficiency of Adjacency List Representation
First the good news:
Enumeration of adjacent nodes Θ(1) per adjacent node
Not so good news:
Takes O(n) to establish if a particular edge is in graph Linear search of adjacency list
Adjacency list length is O(n)
For most of the algorithms we consider here, the adjacency list implementation is preferable.
David Weir (U of Sussex) Program Analysis Term 1, 2015 138 / 192
Vertices and Edges
Let G = (V,E) be a graph where |V| = n and |E| = m
Question: What can we say about |E| in terms of |V|?
How few edges could there be?
Possible that E could be empty, i.e. m = 0 If G is connected then m ≥ n − 1
How many edges could there be?
If G is a complete graph then m = n(n − 1)/2 which is Θ(n2)
So, in general, m is O(n2)
David Weir (U of Sussex) Program Analysis Term 1, 2015 139 / 192
Questions for you
Give adjacency list and adjacency matrix encodings of this graph Which uses the least space?
If this was a complete graph, how many edges would it have?
v2 v5
v1 v4 v7
v3
v6
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
140 / 192
Questions for you
Give adjacency list and adjacency matrix encodings of this graph Which uses the least space?
Adjacency list uses less memory
If this was a complete graph, how many edges would it have?
21
v2 v5
v1 v4 v7
v3
v6
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
140 / 192