Transcript Performance

Data Structures
Heaps and Graphs
i206
Fall 2010
John Chuang
Some slides adapted from Marti Hearst, Brian Hayes, or Glenn Brookshear
Outline
 What is a data structure
 Basic building blocks: arrays and linked lists
 Data structures (uses, methods, performance):
-
List, stack, queue
Dictionary
Tree --> Heap
Graph
John Chuang
2
Heap
 A specialized binary tree that satisfies
- Heap-order property
- Complete binary tree property
 Useful for implementing priority queue,
heap-sort algorithm
John Chuang
3
root node
4,C
Heap
5,A
15,K
16,X
25,J
6,Z
9,F
7,Q
14,E 12,H 11,S
20,B
8,W
last node
 Heap-order property: for every node v other than the
root, the key stored at v is greater than or equal to the
key stored at v’s parent.
 Complete binary tree property: A binary tree with height
h is a complete binary tree if levels 0, 1, 2, …, h-1 of the
tree have the maximum number of nodes, and in level
h-1, all the internal nodes are to the left of the external
nodes, and there is at most one node with one child,
which must be a left child.
John Chuang
4
Heap Methods
 Insert
- Insert element as last node of the heap
- May need to perform up-heap bubbling to restore
heap-order property
 Remove
- Remove and return element at root node
- Move last node to root node
- May need to perform down-heap bubbling to restore
heap-order property
John Chuang
5
Example: Insert(2,T)
4,C
4,C
5,A
15,K
5,A
6,Z
7,Q
9,F
16,X 25,J 14,E 12,H 11,S 8,W
20,B
2,T
15,K
6,Z
16,X 25,J 14,E 12,H 11,S 8,W
5,A
7,Q
16,X 25,J 14,E 12,H 11,S 8,W
John Chuang
5,A
2,T
9,F
2,T
20,B
2,T
4,C
15,K
7,Q
9,F
6,Z
20,B
15,K
4,C
9,F
7,Q
16,X 25,J 14,E 12,H 11,S 8,W
6,Z
20,B
6
Heap Methods
 Insert
- Insert element as last node of the heap
- May need to perform up-heap bubbling to restore
heap-order property
 Remove
- Remove and return element at root node
- Move last node to root node
- May need to perform down-heap bubbling to restore
heap-order property
John Chuang
7
Example: Remove
4,C
4,C
13,W
5,A
15,K
5,A
6,Z
7,Q
9,F
20,B
15,K
6,Z
5,A
13,W
5,A
13,W
6,Z
7,Q
9,F
20,B
15,K
6,Z
20,B
5,A
5,A
9,F
9,F
6,Z
13,W
7,Q
9,F
16,X 25,J 14,E 12,H 11,S
16,X 25,J 14,E 12,H 11,S
15,K
20,B
16,X 25,J 14,E 12,H 11,S
16,X 25,J 14,E 12,H 11,S 13,W
15,K
7,Q
9,F
7,Q
John25,J
Chuang
16,X
14,E 12,H 11,S
20,B
15,K
6,Z
12,H
7,Q
16,X 25,J 14,E 13,W 11,S
20,B
8
Heap Storage
 Heap data easily stored
in contiguous array
root node
4,C
5,A
15,K
16,X 25,J
6,Z
7,Q
9,F
14,E 12,H 11,S
20,B
8,W
last node
John Chuang
4,C
5,A
6,Z
15,K
9,F
[0]
[1]
[2]
[3]
[4]
…
9
Heap Running Times
 What is the running time of each
operation?
 Insert
O(logN)
 Remove
O(logN)
John Chuang
10
Heapsort
 Given an unsorted list of n elements:
- Insert n elements, then
- Remove n elements
 What is run-time of
heapsort algorithm?
 How does it compare
to insertion sort?
http://www.cs.pomona.edu/~marshall/courses/2002/spring/cs50/BigO/
John Chuang
11
Outline
 What is a data structure
 Basic building blocks: arrays and linked lists
 Data structures (uses, methods, performance):
-
List, stack, queue
Dictionary
Tree
Graph
John Chuang
12
Internet Graphs
Source: Cheswick and Burch
John Chuang
13
Social Network Graphs
John Chuang
American Journal of Sociology, Vol. 100, No. 1. "Chains of affection: The structure of
adolescent romantic and sexual networks," Bearman PS, Moody J, Stovel K. 14
Graph
 A graph consists of a set of nodes (vertices) and a set of links
(edges) that establish relationships (connections) between the
nodes
 Represented/stored using adjacency list or adjacency matrix data
structures
- Adjacency list for Graph 1: {a,b}, {a,c}, {b,c}
- Adjacency matrix for Graph 2:
 Edges can be directed/undirected
 Edges can have weights
 Tree is a special case of graph
John Chuang
15
Graph Algorithms
 Search/traversal: breadth-first or depthfirst -- O(|V|+|E|)
 Routing: shortest path between two
points (Dijkstra’s algorithm) -- O(|V|2+|E|)
 Minimum spanning tree -- O(|E|)
 Maximum Flow -- O(|V|3), O(|V|2|E|),
O(|V||E|2)
John Chuang
16
QuickTime™ and a
decompressor
are needed to see this picture.
John Chuang
17
Routing
 Problem: network routers have to forward data
packets toward destination; must determine
next hop
 Algorithm: Dijkstra’s algorithm
-
Shortest Path First (SPF) algorithm
Greedy algorithm
Input: graph with nodes and weighted edges
Output: shortest paths from source node i to every
other node; cost of each path
John Chuang
18
Dijkstra’s Algorithm
John Chuang
Source: Doug Comer
19
Algorithm Intuition
 Start at source node
 Move outward
 At each step:
- Find node u that
- has not been considered before; and
- is closest to source
- Compute:
- Distance from u to each neighbor v
- If distance shorter, make path to v go through u
John Chuang
20
Dijkstra’s Algorithm Example
Distance
Predecessor
John Chuang
21
Node A’s Routing Table
Destination
Address
B
Next Hop
(Cost)
B (2)
C
D (3)
D
D (1)
E
D (2)
F
D (4)
John Chuang
22