SUNY Geneseo Department of Computer Science

Some Uses of Priority Queues

Return to List of Lectures

Misc

Lab 13 due tomorrow (Tuesday)

• Written report

CSci end-of-semester mixer

• Tuesday, May 1, 12:00 - whenever
• South 309

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo
• 5 responses now

Final exam

• Thursday, May 3, 8:00 AM
• Comprehensive but emphasizing material since last hour exam
• Designed for 2 hours, you have 3
• Otherwise similar rules and format to hour exams
• Donuts and cider

Questions?

Priority Queues

"Priority queue" is defined by interface

• PriorityQueue<E extends Comparable>
  • void addItem( E value )
  • E retrieveByPriority()

Frequently implemented as a heap, but that's not essential to being a priority queue

Relation between priority queue and heap is much like relation between dictionary and ordered tree

Some uses of priority queues

• Discrete event simulation
  • Simulate events that happen at discrete times; each event typically triggers others at later times;
  • Examples
    • Banks, toll booths, and similar waiting lines - events are customer arrivals and departures
    • Digital circuits - events are changes in signals

            Simulator
                // keep events in priority queue, by time 'til due
                q.addItem( first event )
                while ( ! q.isEmpty() ) {
                    e = q.retrieveByPriority()
                    process e, e.g.,
                        collect statistics
                        update simulated time
                        create subsidiary events
                            q.addItem( new Event(time) )
                        etc.

Prioritized scheduling

• For example, rendering constructive solid geometry

• Split triangles in order of "importance," under varying definitions of "importance."

        triangulate primitives
        insert triangles into a priority queue
        while queue not empty
            retrieve a triangle
            split it
            insert any sub-triangles into priority queue