CP164 Study Guide - Final Guide: Priority Queue, Optical Fiber, Prims
The Priority Queue ADT
Priority Queue Implementation Choices
Conceptually, how the contents of a Priority Queue are stored is not important. However, as
programmers and software engineers, at some point we have to make a choice of
implementation strategy. The fact that values must be removed from a priority queue in
priority order puts constraints on how we can store Priority Queue contents. (We can't
always on the leprechauns to do the work for us!)
There are two ways to store the contents of a Priority Queue: sorted and unsorted.
Sorted Contents
Advantages
Deletion is simple. Items are sorted by priority so simply remove the item at the
front of the storage list.
Disadvantages
Insertion is difficult. Items must be put into their proper place in the sorted list
when added to the queue.
A linked structure is convenient for this implementation.
Unsorted Contents
Advantage
Insertion is simple. Just add the item to the end of the storage list.
Disadvantage
Deletion is difficult. It is necessary to find the item with the highest priority before it
can be removed.
An array-based structure is convenient for this implementation.
Priority Queues - Applying Prim's Algorithm
Priority Queues can be used to solve certain types of problems in which we want to find the
best possible solution. Some of these types of solutions are called greedy algorithms.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Conceptually, how the contents of a priority queue are stored is not important. However, as programmers and software engineers, at some point we have to make a choice of implementation strategy. The fact that values must be removed from a priority queue in priority order puts constraints on how we can store priority queue contents. (we can"t always on the leprechauns to do the work for us!) There are two ways to store the contents of a priority queue: sorted and unsorted. Items are sorted by priority so simply remove the item at the front of the storage list. Items must be put into their proper place in the sorted list when added to the queue. A linked structure is convenient for this implementation. Just add the item to the end of the storage list. It is necessary to find the item with the highest priority before it can be removed. An array-based structure is convenient for this implementation.
