Gregory M. Kapfhammer

Section 7.1 (Priority Queue Introduction)

• What is a priority queue? Why do you think it might be useful to have this abstract data type?

• Define the notion of a key.

• What is a total order relation? How is a total order relation different than a partial order relation?

---

1. A priority queue is an abstract data type for storing a collection
of prioritized elements that supports arbitrary element insertion but
supports removal of elements in order of priority. This ADT is useful
because it allows us to do things like multithreading. Threads would be executed according to priority.
2. A key is an object that is assigned to an element as a specific
attribute for that element, which can be used to identiy, rank, or
weight that element. In other words, a key is an object used to identify or compare an element.
3. A partial order relation is a relation that is reflexive, antisymmetric, and transitive.
For a comparison rule ¡Ü
Reflexive property: k ¡Ü k
Antisymmetric property: if k1 ¡Ü k2 and k2 ¡Ü k1 , then k1 = k2
Transitive property: if k1 ¡Ü k2 and k2 ¡Ü k3 , then k1 ¡Ü k3
A total order relation is when the comparison rule is defined for every pair of keys.
So a relationship R is total order if it is partial order for R(x,y) or R(y,x) for every x or y in its exact-domain.

Jonathan Goytia

---

1. "A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority; that is, the element with first priority can be removed at any time" (page 286). It is useful to have this abstract data type because elements are stored according to their priorities, not their position.

2. A key is "an object that is assigned to an element as a specific attribute for that element, which can be used to identify, rank, or weight that element" (page 287). A key is assigned to an element and it not necessarily unique. It can be on any type that is appropriate for a particular application.

3. A binary relation R on a set A is a total order relation if and only if it is:
(1) a partial order relation
(2) for any pair of elements a and b of A, R or R. That is, every element is related with every element one way or the other.
A binary relation R on a set A is a partial order relation if and only if it is:
(1) reflexive
(2) antisymmetric
(3) transitive

Brittany Eaves

---

1. A Priority Queue is a container of elements, like a regular Queue, only the elements have associated keys with them that determine their priority, or the order of which they are removed.

2. A key is an object assigned to an element that is used to identify it in a Queue.

3. Total order relation is attained when all the elements in a Queue are ordered in a linear fashion. This way, the comparison between elements will never contradict itself. In a partial order relation, some elements are not in linear order and comparisons may have contradictions.

Jesse Hixson

---

---

Link to this Page

• Priority Queues last edited on 29 April 2003 at 10:24 am by alden28.alleg.edu