Priority Queues (Chapter 9)

Question 1

What is an entry in terms of priority queue? Name the two methods associated with the entries.

Answer 1

An entry is a key-value pair that allows for efficient insertion and removal based on keys.

key() : returns a key for this entry
value(): returns a value for this entry

Question 1

What is an entry in terms of priority queue? Name the two methods associated with the entries.

Answer 1

An entry is a key-value pair that allows for efficient insertion and removal based on keys.

key() : returns a key for this entry
value(): returns a value for this entry

Question 2

Describe what total order relations are within the context of PQs

Answer 2

Criteria that a key must meet/comply with in order to be comparable

Question 3

Name and give a formula for the 3 different total order relations

Answer 3

1. Reflexivity: x <= x
2. Antisymmetric: if x <=y and y<= x then x = y
   3, Transitivity: if x<= y and y <= z then x<= z

Question 4

Name 3 applications of PQs to the real world

Answer 4

1. Stand by flyers (if you were to miss a flight you get attended to based on how important you are to the flight company )
2. Auctions (you are prioritized based on the amount of money you are willing to pay for an item)
3. Stock Market (the more money you have, the more valuable you become)

Question 5

What does the comparator ADT do?

Answer 5

It encapsulates the comparison of two objects according to a given total order relation

Question 6

Describe how the comparator main method compare(x,y) works

Answer 6

it works by returning an integer based on how 2 objects relate to one another. it will return i>0 if x > y, it will return i = 0 if x =y, it will return i < 0 if x < y otherwise give an error if x and y cannot be compared.

Question 7

What two main methods are associated with PQs?

Answer 7

insert(k,v) and removeMin()

Question 7

What two main methods are associated with PQs?

Answer 7

insert(k,v) and removeMin()

Question 8

Discuss the difference in the performance of the two main methods of PQ when implemented with an unsorted list vs a sorted list

Answer 8

Usorted List:

1. insert() will be O(1), this is because it is simply inserted without being specifically arranged
2. removeMin() will be O(n) in worst time since the whole collection will have to be traversed through in order to be selected as the next minimum in the collection

Question 9

Discuss the difference in the performance of the two main methods of PQ when implemented with a sorted list

Answer 9

1. insert() will be O(n) as the list will need to be traversed through in order to find the correct place to insert the element
2. removeMin() will be O(1) since the minimum will be at the beginning

Question 10

Name and give a brief explanation of the 2 variations of PQ sort. Also, state the runtime of their different phases and the overall runtime

Answer 10

1. Selection sort, implemented with an unsorted list
   phase 1: O(1)n = O(n)
   phase 2: O(n)n = O(n^2)
   OVERALL: O(n^2)
2. Insertion sort implemented with a sorted list
   phase 1: O(n)n = O(n^2)
   phase 1: O(1)n = O(n)
   OVERALL: O(n^2)

Question 11

What is in-place insertion-sort and how does it work?

Answer 11

It is a way of sorting a PQ without the use of an external data structure like a LL in the case of selection and insertion sort.

It works by keeping a portion of the queue sorted and swapping out of order elements