CSE 373

Java Collection Framework, Part 2:

Priority Queue, Map

slides created by Marty Stepp

http://www.cs.washington.edu/373/

© University of Washington, all rights reserved.

1
 Priority queue ADT
• priority queue: a collection of ordered elements that provides fast
access to the minimum (or maximum) element
 usually implemented using a tree structure called a heap

• priority queue operations:

 add adds in order; O(log N) worst
 peek returns minimum value; O(1)
always
 remove removes/returns minimum value; O(log N)
worst
 isEmpty,
clear,
size,
iterator O(1) always
2
 Java's PriorityQueue class
public class PriorityQueue<E> implements Queue<E>
Method/Constructor Description Runtime
PriorityQueue<E>() constructs new empty queue O(1)
add(E value) adds value in sorted order O(log N )
clear() removes all elements O(1)
iterator() returns iterator over elements O(1)
peek() returns minimum element O(1)
remove() removes/returns min element O(log N )

Queue<String> pq = new PriorityQueue<String>();

pq.add("Stuart");
pq.add("Marty");
...
3
 Priority queue ordering
• For a priority queue to work, elements must have an ordering
 in Java, this means implementing the Comparable interface
• many existing types (Integer, String, etc.) already implement this
• if you store objects of your own types in a PQ, you must implement it
 TreeSet and TreeMap also require Comparable types

public class Foo implements Comparable<Foo> {

…
public int compareTo(Foo other) {
// Return > 0 if this object is > other
// Return < 0 if this object is < other
// Return 0 if this object == other
}
}

4
 The Map ADT
• map: Holds a set of unique keys and a collection of values, where
each key is associated with one value.
 a.k.a. "dictionary", "associative array", "hash"

• basic map operations:

 put(key, value): Adds a
mapping from a key to
a value.

 get(key): Retrieves the

value mapped to the key.

 remove(key): Removes
the given key and its myMap.get("Juliet") returns "Capulet"
mapped value.
5
 Map concepts
• a map can be thought of as generalization of a tallying array
 the "index" (key) doesn't have to be an int

 count digits: 22092310907 index 0 1 2 3 4 5 6 7 8 9

value 3 1 3 0 0 0 0 1 0 2

// (R)epublican, (D)emocrat,
(I)ndependent
 count votes: "RDDDDRRRRRDDDDDDRDRRIRDRRIRDRRID"
"R" 14
key "R" "D" "I"
"D" 3
value 15 14 3
"I" 15
keys values

6
 Map implementation
• in Java, maps are represented by Map interface in java.util

• Map is implemented by the HashMap and TreeMap classes

 HashMap: implemented using an array called a "hash table";
extremely fast: O(1) ; keys are stored in unpredictable order

 TreeMap: implemented as a linked "binary tree" structure;

very fast: O(log N) ; keys are stored in sorted order

 A map requires 2 type parameters: one for keys, one for values.

// maps from String keys to Integer values

Map<String, Integer> votes = new HashMap<String, Integer>();

7
 Map methods
put(key, value) adds a mapping from the given key to the given value;
if the key already exists, replaces its value with the given one
get(key) returns the value mapped to the given key (null if not found)
containsKey(key) returns true if the map contains a mapping for the given key
remove(key) removes any existing mapping for the given key
clear() removes all key/value pairs from the map
size() returns the number of key/value pairs in the map
isEmpty() returns true if the map's size is 0
toString() returns a string such as "{a=90, d=60, c=70}"

keySet() returns a set of all keys in the map

values() returns a collection of all values in the map
putAll(map) adds all key/value pairs from the given map to this map
equals(map) returns true if given map has the same mappings as this one

8
 Using maps
• A map allows you to get from one half of a pair to the other.
 Remembers one piece of information about every index (key).

// key value
put("Joe", "206-685-2181")
Map

 Later, we can supply only the key and get back the related value:
Allows us to ask: What is Joe's phone number?

get("Joe")
Map
"206-685-2181"

9
 Maps vs. sets
• A set is like a map from elements to boolean values.
 Set: Is Joe found in the set? (true/false)

"Joe" true
Set
false

 Map: What is Joe's phone number?

"Joe" "206-685-2181"
Map

10
 keySet and values
• keySet method returns Set of all keys in map
 can loop over the keys in a foreach loop
 can get each key's associated value by calling get on the map
Map<String, Integer> ages = new TreeMap<String, Integer>();
ages.put("Joe", 57);
ages.put("Geneva", 2); // ages.keySet() returns Set<String>
ages.put("Vicki", 19);
for (String name : ages.keySet()) { // Geneva -> 2
int age = ages.get(name); // Joe -> 57
System.out.println(name + " -> " + age); // Vicki -> 19
}

• values method returns Collection of all values in map

 ages.values() above returns [2, 57, 19]
 can loop over the values with a for-each loop
 no easy way to get from a value back to its associated key(s)
11
 Collections summary
collection ordering benefits weaknesses
array by index fast; simple little functionality;
cannot resize
ArrayList by insertion, by index random access; fast slow to modify in
to modify at end middle/front
LinkedList by insertion, by index fast to modify at both poor random access
ends
TreeSet sorted order sorted; O(log N) must be comparable
HashSet unpredictable very fast; O(1) unordered
LinkedHashSet order of insertion very fast; O(1) uses extra memory
TreeMap sorted order sorted; O(log N) must be comparable
HashMap unpredictable very fast; O(1) unordered
LinkedHashMap order of insertion very fast; O(1) uses extra memory
PriorityQueue natural/comparable fast ordered access must be comparable

 It is important to be able to choose a collection properly based on the

capabilities needed and constraints of the problem to solve.
12
 Choosing a collection

 see also: http://initbinder.com/bunker/wp-content/uploads/2011/03/collections.png

13
 Compound collections
• You will often find that you want a collection of collections:
 a list of lists; a map of strings to lists; a queue of sets; ...

• Example: how would you store people's friends?

 i.e., I need to quickly look up the names of all of Jimmy's buddies,
or test whether a given person is a friend of Jimmy's or not.

// don't forget to initialize each Set of friends

Map<String, Set<String>> pals =
new HashMap<String, Set<String>>();
pals.put("Jimmy", new HashSet<String>());
pals.get("Jimmy").add("Bill");
pals.get("Jimmy").add("Katherine");
pals.get("Jimmy").add("Stuart");

14
 Iterators (11.1)
• iterator: An object that allows a client to traverse the elements of
any collection.
 Remembers a position, and lets you:
• get the element at that position
• advance to the next position
• remove the element at that position

index 0 1 2 3 4 5 6 7 8 9 "the"
list value 3 8 9 7 5 12 0 0 0 0 set "to" "we"
size 6 "from"

current element: 9 current element: "from"

iterator iterator
current index: 2 next element: "the"

15
 Iterator methods
hasNext() returns true if there are more elements to examine
next() returns the next element from the collection (throws a
NoSuchElementException if there are none left to examine)
remove() removes the last value returned by next() (throws an
IllegalStateException if you haven't called next() yet)

• Iterator interface in java.util

 every collection has an iterator() method that returns an iterator
over its elements

Set<String> set = new HashSet<String>();

...
Iterator<String> itr = set.iterator();
...
16
 Iterator example
Set<Integer> scores = new TreeSet<Integer>();
scores.add(94);
scores.add(38); // Jenny
scores.add(87);
scores.add(43); // Marty
scores.add(72);
...

Iterator<Integer> itr = scores.iterator();

while (itr.hasNext()) {
int score = itr.next();

System.out.println("The score is " + score);

// eliminate any failing grades

if (score < 60) {
itr.remove();
}
}
System.out.println(scores); // [72, 87, 94]
17
 A surprising example
• What's bad about this code?
List<Integer> list = new LinkedList<Integer>();
... (add lots of elements) ...
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}

data next data next data next

front = 42 -3 17
element 0 element 1 element 2

18
 Iterators and linked lists
• Iterators are particularly useful with linked lists.
 The previous code is O(N2) because each call on get must start from
the beginning of the list and walk to index i.
 Using an iterator, the same code is O(N). The iterator remembers its
position and doesn't start over each time.

data next data next data next

front = 42 -3 17
element 0 element 1 element 2

current element: -3
iterator
current index: 1
19
 ListIterator
add(value) inserts an element just after the iterator's position
hasPrevious() true if there are more elements before the iterator

nextIndex() the index of the element that would be returned the next time
next is called on the iterator
previousIndex() the index of the element that would be returned the next time
previous is called on the iterator
previous() returns the element before the iterator (throws a
NoSuchElementException if there are none)
set(value) replaces the element last returned by next or previous with
the given value

ListIterator<String> li = myList.listIterator();

• lists have a more powerful ListIterator with more methods

 can iterate forwards or backwards
 can add/set element values (efficient for linked lists) 20