Program Analysis
Review of Priority Queues and Graphs
David Weir (U of Sussex) Program Analysis Term 1, 2017 79 / 606
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, 2017 80 / 606
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, 2017 81 / 606
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, 2017 82 / 606
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, 2017 83 / 606
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, 2017 84 / 606
Implementations of Priority Queues
We will consider two alternatives:
Unsorted list implementation
Heap implementation
David Weir (U of Sussex) Program Analysis Term 1, 2017 85 / 606
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, 2017 86 / 606
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 Θ(n) time in worst-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, 2017 87 / 606
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
leftmost grandchild
of root
David Weir (U of Sussex) Program Analysis Term 1, 2017 88 / 606
Heaps
In general:
a1 . . . ai . . . a2i a2i+1 . . . an
root of
tree
some node
within tree
left child
of ai
right child
of ai
David Weir (U of Sussex) Program Analysis Term 1, 2017 89 / 606
Heap as Tree
a1
a2
a4
a8 a9
a5
a10 a11
a3
a6
a12 a13
a7
a14 a15
David Weir (U of Sussex) Program Analysis Term 1, 2017 90 / 606
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, 2017 91 / 606
Example Heap
98
97
14
10 13
88
70 1
20
15
12 13
10
3 2
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, 2017 92 / 606
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, 2017 93 / 606
Adding a New Element
98
97
14
10
50
13
88
70 1
20
15
12 13
10
3 2
98 97 20 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, 2017 94 / 606
Exchange with Parent
98
97
14
50
10
13
88
70 1
20
15
12 13
10
3 2
98 97 20 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, 2017 95 / 606
Exchange with Parent
98
97
50
14
10
13
88
70 1
20
15
12 13
10
3 2
98 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, 2017 96 / 606
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 Θ(log n) in worst-case
Best-case running time is Θ(1)
David Weir (U of Sussex) Program Analysis Term 1, 2017 97 / 606
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, 2017 98 / 606
Illustrative Example
98
97
50
14
10
13
88
70 1
20
15
12 13
10
3 2
98 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, 2017 99 / 606
Remove Root
97
50
14
10
13
88
70 1
20
15
12 13
10
3 2
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, 2017 100 / 606
Insert Last Element at Root
10
97
50
14 13
88
70 1
20
15
12 13
10
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, 2017 101 / 606
Compare Root with Children
10
97
50
14 13
88
70 1
20
15
12 13
10
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, 2017 102 / 606
Left Child Should be Root
10
97
50
14 13
88
70 1
20
15
12 13
10
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, 2017 103 / 606
Swop Root and Left Child
97
10
50
14 13
88
70 1
20
15
12 13
10
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, 2017 104 / 606
Compare with Children
97
10
50
14 13
88
70 1
20
15
12 13
10
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, 2017 105 / 606
Right Child Should Move Up
97
10
50
14 13
88
70 1
20
15
12 13
10
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, 2017 106 / 606
Swop Nodes
97
88
50
14 13
10
70 1
20
15
12 13
10
3 2
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, 2017 107 / 606
Compare with Children
97
88
50
14 13
10
70 1
20
15
12 13
10
3 2
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, 2017 108 / 606
Left Child Should Move Up
97
88
50
14 13
10
70 1
20
15
12 13
10
3 2
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, 2017 109 / 606
Swop Nodes
97
88
50
14 13
70
10 1
20
15
12 13
10
3 2
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, 2017 110 / 606
Restored the Heap
97
88
50
14 13
70
10 1
20
15
12 13
10
3 2
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, 2017 111 / 606
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, 2017 112 / 606
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
57
22 43
59
10 16
75
21
20 13
30
17 2
David Weir (U of Sussex) Program Analysis Term 1, 2017 112 / 606
Running Time
How Long Does This Take?
Worst-case bounded by depth of tree, so Θ(log n)
Best-case Θ(1)
David Weir (U of Sussex) Program Analysis Term 1, 2017 113 / 606
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, 2017 114 / 606
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, 2017 115 / 606
Heapification Order
44
32
37
94 25
75
48 19
65
15
58 72
29
23 11
44 32 65 37 75 15 29 94 25 48 19 58 72 23 11
height 3 2 2 1 1 1 1 0 0 0 0 0 0 0 0
David Weir (U of Sussex) Program Analysis Term 1, 2017 116 / 606
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, 2017 117 / 606
Total Running Time
⌈log n⌉
∑
h=0
n
2h+1
O(h) =
1
2
n
⌈log n⌉
∑
h=0
1
2h
O(h)
= O
n
⌈log n⌉
∑
h=0
h
2h
= O(n)
note that
∞
∑
h=0
h
2h
converges to 2
David Weir (U of Sussex) Program Analysis Term 1, 2017 118 / 606
Review of Graphs
David Weir (U of Sussex) Program Analysis Term 1, 2017 119 / 606
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, 2017 120 / 606
Graphs: Examining an Example
Let’s look at an example graph
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
There are 8 vertices or nodes
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
Use n to refer to the number of nodes — so n = 8
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
Use V to refer to the set of all nodes — so V = {v1, . . . , v8}
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
There are 10 edges
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
Each edge denoted by a set of two vertices
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
For example: {v5, v7}
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
Use m to refer to the number of edges — so m = 10
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
Use E to refer to the set of all edges
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
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 Term 1, 2017 121 / 606
Graphs: Examining an Example
Use G to refer to the graph — so G = (V ,E)
v1
v2
v3
v4
v5
v6
v7
v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1
v2
v3
v4
v5
v6
v7
v8
The layout of the graph is unimportant
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
Graphs: Examining an Example
v1v2
v3v4
v5
v6
v7v8
This is the same graph
David Weir (U of Sussex) Program Analysis Term 1, 2017 121 / 606
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, 2017 122 / 606
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, 2017 123 / 606
Directed Graphs
v1v2
v3v4
v5
v6
v7v8
Sometimes relationships are directional
David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606
Directed Graphs
v1v2
v3v4
v5
v6
v7v8
Capture this with directional edges
David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606
Directed Graphs
v1v2
v3v4
v5
v6
v7v8
This is called a directed graph
David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606
Directed Graphs
v1v2
v3v4
v5
v6
v7v8
E is now a set of directed pairs
David Weir (U of Sussex) Program Analysis Term 1, 2017 124 / 606
Directed Graphs
v1v2
v3v4
v5
v6
v7v8
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, 2017 124 / 606
Directed Acyclic Graphs
v1v2
v3v4
v5
v6
v7v8
Important special case: directed acyclic graphs or DAGs
David Weir (U of Sussex) Program Analysis Term 1, 2017 125 / 606
Weighted Graphs
v1v2
v3v4
v5
v6
v7v8
Sometimes want to associate weights with edges – e.g. distance
David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606
Weighted Graphs
v1v2
v3v4
v5
v6
v7v8
Capture this with weighted edges
David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606
Weighted Graphs
v1v2
v3v4
v5
v6
v7v8
15
2
40
8
11
1429
41 33
6
This is called a weighted graph
David Weir (U of Sussex) Program Analysis Term 1, 2017 126 / 606
Trees: A Special Kind of Graph
v1v2
v3v4
v5
v6
v7v8
Let’s remove these edges to give a tree
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3v4
v5
v6
v7v8
How can we tell that its a tree?
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3v4
v5
v6
v7v8
Let’s pick it up by v8
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
What happens if we put back the edges we removed
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Adding that one creates a cycle
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Adding that one also creates a cycle
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Guess what!
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Fact 1: there are no cycles
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Fact 2: its connected, i.e. path between any pair of nodes
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
Fact 3: n nodes and n − 1 edges
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
Trees: A Special Kind of Graph
v1v2
v3 v4
v5 v6
v7
v8
. . . and that’s what makes it a tree
David Weir (U of Sussex) Program Analysis Term 1, 2017 127 / 606
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, 2017 128 / 606
Adjacency Matrix Representation
Adjacency matrix for undirected graph shown earlier
v1 v2 v3 v4 v5 v6 v7 v8
v1 0 1 1 0 0 0 0 0
v2 1 0 1 0 1 0 0 0
v3 1 1 0 0 0 1 0 0
v4 0 0 0 0 0 1 1 0
v5 0 1 0 0 0 0 1 1
v6 0 0 1 1 0 0 0 1
v7 0 0 0 1 1 0 0 0
v8 0 0 0 0 1 1 0 0
Entry value in (i , j) same as value in (j , i) for undirected graph
David Weir (U of Sussex) Program Analysis Term 1, 2017 129 / 606
Adjacency Matrix Representation
Adjacency matrix for directed graph shown earlier
v1 v2 v3 v4 v5 v6 v7 v8
v1 0 1 0 0 0 0 0 0
v2 0 0 1 0 1 0 0 0
v3 1 0 0 0 0 0 0 0
v4 0 0 0 0 0 0 0 0
v5 0 0 0 0 0 0 1 0
v6 0 0 1 1 0 0 0 1
v7 0 0 0 1 0 0 0 0
v8 0 0 0 0 1 0 0 0
David Weir (U of Sussex) Program Analysis Term 1, 2017 130 / 606
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, 2017 131 / 606
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, 2017 132 / 606
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, 2017 133 / 606
Adjacency List Representation
v8
v7
v6
v5
v4
v3
v2
v1 v2 v3
v1 v4 v5
v1 v2 v6
v6 v7
v2 v7 v8
v3 v4 v8
v4 v5
v5 v6
David Weir (U of Sussex) Program Analysis Term 1, 2017 134 / 606
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, 2017 135 / 606
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, 2017 136 / 606
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, 2017 137 / 606
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, 2017 138 / 606
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?
v1
v2
v3
v4
v5
v6
v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 139 / 606
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
v1
v2
v3
v4
v5
v6
v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 139 / 606