Abstract Priortiy Queues

Outline

• Review queus
• Two implelementation ways
  • Array of queues

Review

• Abstract lists

Introduction to Priority-Queus

• Definition: use some keys

• Example numeric priority based on $x$

  • $0$ has the highest priority
  • if $x>y$, $x$ has hiegher priority than $y$

• Example Lexicographic Priority

Some applications

• Processes requesting hardware components have prioirty

  Linux nice command: -20 highest priority and 19 means lowest prioirty

  $ nice -20 ./a.out
  

Implementations

• Using an array of queues
• Using an AVL tree
• Using heaps

Implement using an array of queues

• Have an array with indexes from $0-M$. Each element points to a priority queue.

template <typename Type>
void Multiqueue<Type>::push(Type const &obj, int, pri) {
    if (pri > 0 || pri >=M) {
        throw illegal_argument();
    }

    ...
}

Analysis

*

Implement using an AVL tree

template<typename Type>
class AVL_priority_queue() {

}

bool AVL_priority_queue<Type>::empty() const {

}