CSE 214 Computer Science II (Spring 2015)

RECITATION 10 – Priority Queue

Objective:

1. To Study Priority Queue

1. [10 min] Illustrate the execution of the selection-sort algorithm using priority queue on the following input sequence:

(22, 15, 36, 44, 10, 3, 9, 13, 29, 25).

2. [10 min]  Which data structure should be used for the given operations? Why?

          An airport is developing a computer simulation of air-traffic control that handles events such as landings and takeoffs. Each event has a time stamp that denotes the time when the event will occur. The simulation program needs to efficiently

                 perform the following two fundamental operations:

                  • Insert an event with a given timestamp (that is, add a future event).

                  • Extract the event with a smallest timestamp (that is, determine the next event to process).

3. [10 min] Give an example of a worst-case sequence with n elements for insertion-sort, and show that insertion-sort runs in Ω(n2) time on such a sequence.

4. [10 min] Give the complexity of the following operations

1. Insertion(): Priority Queue implemented using Linklist
2. Insertion(): Priority Queue implemented using Binary Search Tree
3. removeMin():Priority Queue implemented using Linklist
4. removeMin():Priority Queue implemented using Binary Search Tree

5. [10 min] What does each removeMin call return within the following sequence of priority queue ADT operations:

insert(5, A), insert(4, B), insert(7, F), insert(1, D), removeMin( ), insert(3, J), insert(6, L), removeMin( ), removeMin( ), insert(8, G), removeMin( ), insert(2, H), removeMin( ), removeMin( )?