Priority Queue

What is a Priority Queue?

Priority Queues

Stores prioritized elements • No notion of storing at particular position

Returns elements in priority order • Order determined by key

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

What’s so different? Stacks and Queues • Removal order determined by order of inserting

Sequences • User chooses exact placement when inserting and explicitly chooses removal order

Priority Queue • Order determined by key • Key may be part of element data or separate Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

College Admissions Key Student submits: • Personal data (geography, is parent alum?, activities?) • Transcript • Essays • Standardized test scores • Recommendations

Admissions agent: • Each datum converted to number • Formula converts to single numeric key Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

What’s it good for? Order of returned elements is not FIFO or LIFO (as in queue or stack) Random access not necessary (as in sequence) or desirable Examples • Plane landings managed by air traffic control • Processes scheduled by CPU • College admissions process for students —What are some of the criteria? Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Student selection process Simple scheme • Collect applications until due date • Sort by keys • Take top k students

More realistic • Prioritize applications as they come in • Accept some top students ASAP • Maybe even change data/key as you go Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

1

Priority Queue ADT insertItem(k,e): insertItem(k,e): insert element e with key k extractMin( extractMin( ): return element with minimum key and remove from queue

Keys, Comparitors and Total Orders Key type needs comparison operator (returns boolean) boolean) with following properties: • Reflexive: k ≤ k

minElement( minElement( ): return (look at) min element

• Antisymmetric: Antisymmetric: (k1 ≤ k2) && (k2 ≤ k1) → k1 = k2

minKey( minKey( ): return minimum key

• Transitive: ((k1 ≤ k2) && (k2 ≤ k3) → k1 ≤ k3

size( ): return number of elements isEmpty( isEmpty( ): size == 0? Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Abstracting Comparitors Allows for different types of comparison • e.g. Numeric vs. vs. lexicographic (for strings)

Several approaches possible • Build PQ object to know about specific key type and comparison • Build key object to know about comparison • Build separate comparitor object for each type of comparison

Book argues for #3, but I also recommend #2 Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Implementing PQ with Sorted Sequence Each call to insertItem(k, insertItem(k, e) traverses sorted sequence to find correct position, then does insert • O(n) worst case

Each call to extractMin( extractMin( ) does removeFirst( removeFirst( ) • O(1) time Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

These properties guarantee consistent, total ordering Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Implementing PQ with Unsorted Sequence Each call to insertItem(k, insertItem(k, e) uses insertLast( insertLast( ) to store in Sequence • O(1) time

Each call to extractMin( extractMin( ) traverses the entire sequence to find the minimum, then removes element • O(n) time Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Sorting Using a PQ Elements begin in arbitrary order in a sequence Move elements from sequence into PQ Extract elements from PQ and reinsert into sequence in priority order Analysis depends on implementation choices Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

2

Analyzing Queue Efficiency for Sorting

Selection Sort PQ sorting using unsorted sequence

N insertElement( insertElement( ) operations followed by N extractMin( extractMin( ) operations

Insert all n items in input order Extract by selecting min item n times

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Insertion Sort

Sort Analysis Sel. Sel. Sort

PQ sorting using sorted sequence

foreach element, Ei, in S O(n)

i=0

ΣO(i)

i=ni=n-1

i=ni=n-1

i=0

i=0

i=ni=n-1

i=ni=n-1

i=0

i=0

ΣO(i)

PQ.extractMin () PQ.extractMin()

Extract items easily from sorted sequence

i=ni=n-1

i=0

O(n)

while !PQ.empty()

Sequentially insert items into sequence in sorted order

i=ni=n-1

Σ O(1)

PQ.insert(E PQ.insert(Ei)

Ins. Sort

Σ O(1)

O(n) + ΣO(1) + ΣO(i) = O(n) + O(n) + O(n2) = O(n2)

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Heap

Heap Example

Binary treetree-based data structure 10

• Complete in the sense that it fills up levels as completely as possible • Height of tree is O(logn) logn)

15

Stores elements with keys All nodes satisfy the heap property: property: • The key value at a node is less than or equal to the key value of the node’s children

Allows insertItem( insertItem( ) and extractMin( extractMin( ) in O(logn) logn) time Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

20 17

19 31

32

22

25 21

30

35

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

3

PQ Quiz Show!

Heap, or Not a Heap? a g

Heap, or Not A Heap?

c i

h

e

(no paper necessary) q

n

p

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

w

Heap, or Not a Heap?

f

c

j

k

v k p

x

s

w m

f

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Heap, or Not a Heap?

n

k

s

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

m

q

z

y

f

p

j

r

v

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Heap, or Not a Heap?

Inserting into Heap Create new node as “last” element

1

Insert key/element into new node 3 20

5 32

6

8

Bubble node upward until heap property is satisfied while (!isRoot (node) && (!isRoot(node) (node.key < node.parent.key)) swap(node, parent) (just pseudocode - can’t do it exactly like this in Java)

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

4

Heap Insert Example

Bubble Upward

10

10

15 17

19 22

32

31

15

20 25 21

22

32

31

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

21

7

15

15

7 17

32

22

20 21

25

Bubble Upward

10

31

35

30

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Bubble Upward

19

7

17

19

30 7

35

20

35

30 25

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Heap Insert Analysis

10 17

19 31

32

22

20 21

35

30 25

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Extracting from Heap Copy element from root node

New node always inserted at lowest level

Copy element/key from last node to root node

Node bubbles upward

Delete last node

• up to root in worst case • path length to root is O(logn logn)

Total time for insert is O(logn logn)

Bubble root node downward until heap property satisfied while (!isExternal (node) && (!isExternal(node) (node.key > node.smallestChild .key)) node.smallestChild.key)) swap(node, node.smallestChild ) node.smallestChild)

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

5

Heap Extract Example

Copy Extracted Element 7

7 15 17

19 22

32

31

15

10

21

35

25

17

19

30

20

22

32

31

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

7

17 22

32

31

20 21

35

17 22

32

7

25 21

35

35

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

10

15

20

22

21

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

10

17

30

20

All done

15

31

25

32

31

Bubble Downward

19

25

10

19

30

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

7

35

15

10

19

21

Bubble Downward

25

15

30

20

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Move last node to root 7

10

30

20 17

19 31

32

22

25 21

30

35

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

6

Heap Extract Analysis

Sort Analysis Heap Sort foreach element, Ei, in S O(n)

i=ni=n-1

Σ O(logi logi)

PQ.insert(E PQ.insert(Ei)

Again, each swap takes constant time Maximum swaps is path length from root to leaf

while !PQ.empty()

i=0

O(n) i=ni=n-1

ΣO(logi logi)

PQ.extractMin () PQ.extractMin()

i=0

i=ni=n-1

i=ni=n-1

i=0

i=0

O(n) +2 ΣO(logi logi) < O(n) + 2 ΣO(logn logn)

→ Total work is logn logn * O(1) = O(logn logn)

= O(n) + 2n*O 2n*O((logn logn) = O( O(nlogn logn) (showing θ (nlogn logn) is a bit harder) Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

InIn-class Exercise

What does the heap look like after the following sequence of insertions: 5

30

2

15

7

45

20

6

18

Johns Hopkins Department of Computer Science Course 600.226: Data Structures, Professor: Jonathan Cohen

7