Abstract Priortiy Queues

Outline

Definition
Two implelementation ways
- Array of queues

Introduction to Priority-Queues

Definition: A priority queue is an ADT where each object placed into the priority queue has a priority value. The objects can be retrieved via top or pop but the object with the highest priority is retrieved first.
push places a new object in an appropriate location based on its priority
pop remove the current highest priority object

Examples of priority types:

Numeric priority based on $x$ (lower value has higher prioirty)
- $0$ has the highest priority
- if $x>y$, $x$ has hiegher priority than $y$
Example Lexicographic Priority: Given a key pair such as $(a,b)$, we say that the $(a,b)$ has higher priority than $(c,d)$ if
- $a < b$
- $a=b \text{ and } c<d$

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 $M$ indexes from $0$ to $M-1$. Each element points to a queue.
When a new object comes, it will be pushed to one of the $M$ queues according to its priority.

#include "myqueue.h"

template<typename Type, int M>
class MultiQueue {
    private: 
        Queue<Type> queue_array[M];
        int queue_size;
    public:
        MultiQueue();
        bool isempty() const;
        Type top() const;
        void push(const Type &, int);
        Type pop();
};

constructor

template<typename Type, int M>
MultiQueue<Type>::MultiQueue() : queue_size( 0 ) {
    // empty constructor
}

isempty()

template<typename Type, int M>
bool MultiQueue<Type>::isempty() {
    return (queue_size == 0);
}

top()

template<typename Type, int M>
Type MultiQueue<Type>::top() {
    for (int pri = 0; pri < M; ++pri) {
        if (!queue_array[pri].isempty()) {
            return queue_array[pri].front();
        }
    }

    throw underflow;
}

pop()

template<typename Type, int M>
Type MultiQueue<Type>::pop() {
    for (int pri = 0; pri < M; ++pri) {
        if (!queue_array[pri].isempty()) {
            -- queue_size;
            return queue_array[pri].pop();
        }
    }

    throw underflow;
}

push()

template<typename Type, int M>
void MultiQueue<Type>::push(const Type & obj, int pririty) {
    if (priority < 0 || priority >= M) {
        throw illegal_argument;
    }
    queue_array[priority].push(obj);
    ++queue_size;
}

Analysis

push is $\Theta(1)$
top and pop: $\Theta(M)$
memory requirement $\Theta(n + M)$
restricing the range of priorities

Implement using an AVL tree

template<typename KeyType, typename RecType>
class AVL_tree;

template<typename Type>
class AVL_priority_queue() {
    private:
        AVL_tree<int, Type> tree; // keytype=int
    public:
        bool isempty() const;
        Type top() const;
        Type pop();
        void push(const Type &, int);
}

isempty()

bool AVL_priority_queue<Type>::isempty() const {
    return tree.isempty();
}

top()

Type AVL_priority_queue<Type>::top() const {
    return tree.retrieve( tree.front() );
}

push()

void AVL_priority_queue<Type>::push(const Type &obj, int k) {
    tree.insert(k, obj);
}

pop()

Type AVL_priority_queue<Type>::pop() {
    Type obj = tree.front();
    tree.erase(obj);
    return obj;
}

Analysis

push $\Theta(\ln(n))$
pop $\Theta(\ln(n))$