Web Analytics Made Easy - StatCounter

Priority Queues (with code in C, C++, and Java)

Introduction

Regular queue follows a First In First Out (FIFO) order to insert and remove an item. Whatever goes in first, comes out first. However, in a priority queue, an item with the highest priority comes out first. Therefore, the FIFO pattern is no longer valid.

Every item in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. If the two items have same priorities, the order of removal is undefined and it depends upon the implementation.

The real world example of a priority queue would be a line in a bank where there is a special privilege for disabled and old people. The disabled people have the highest priority followed by elderly people and the normal person has the lowest priority.

Operations on a priority queue

Just like the regular queue, priority queue as an abstract data type has following operations.

  1. EnQueue: EnQueue operation inserts an item into the queue. The item can be inserted at the end of the queue or at the front of the queue or at the middle. The item must have a priority.
  2. DeQueue: DeQueue operation removes the item with the highest priority from the queue.
  3. Peek: Peek operation reads the item with the highest priority.

The complexity of these operation depends upon the underlying data structure being used.

Implementation

A priority queue can be implemented using data structures like arrays, linked lists, or heaps. The array can be ordered or unordered.

Using an ordered array

The item is inserted in such a way that the array remains ordered i.e. the largest item is always in the end. The insertion operation is illustrated in figure 1.

Fig 1: Insertion operation in an ordered array

The item with priority 7 is inserted between the items with priorities 6 and 8. We can insert it at the end of the queue. If we do so the array becomes unordered. Since we must scan through the queue in order to find the appropriate position to insert the new item, the worst-case complexity of this operation is O(n). Since the item with the highest priority is always in the last position, the dequeue and peek operation takes a constant time. The C program below implements the enqueue and dequeue operation using an ordered array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// insert an item at the appropriate position of the
// queue so that the queue is always ordered
void enqueue(int item) {
        // Check if the queue is full
        if (n == MAX_SIZE - 1) {
                printf("%s\n", "ERROR: Queue is full");
                return;
        }

        int i = n - 1;
        while (i >= 0 && item < queue[i]) {
                queue[i + 1] = queue[i];
                i--;
        }
        queue[i + 1] = item;
        n++;
}

// remove the last element in the queue
int dequeue() {
        int item;
        // Check if the queue is empty
        if (n == 0) {
                printf("%s\n", "ERROR: Queue is empty");
                return -999999;
        }
        item = queue[n - 1];
        n = n - 1;
        return item;
}

Using an unordered array

We insert the item at the end of the queue. While inserting, we do not maintain the order. The complexity of this operation is O(1). Since the queue is not ordered, we need to search through the queue for the item with maximum priority. Once we remove this item, we need to move all the items after it one step to the left. The dequeue operation is illustrated in figure 2.

Fig 2: Dequeue operation in an unordered array

It is obvious that the complexity of dequeue and peek operation is O(n). The following C program implements the priority queue using an unordered array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// insert an item at the rear of the queue
void enqueue(int item) {
        // Check if the queue is full
        if (n == MAX_SIZE - 1) {
                printf("%s\n", "ERROR: Queue is full");
                return;
        }
        queue[n++] = item;
}

// removes the item with the maximum priority
// search the maximum item in the array and replace it with 
// the last item
int dequeue() {
        int item;
        // Check if the queue is empty
        if (n == 0) {
                printf("%s\n", "ERROR: Queue is empty");
                return -999999;
        }
        int i, max = 0;
        // find the maximum priority
        for (i = 1; i < n; i++) {
                if (queue[max] < queue[i]) {
                        max = i;
                }
        }
        item = queue[max];

        // replace the max with the last element
        queue[max] = queue[n - 1];
        n = n - 1;
        return item;
}

Using a linked list

The linked can be ordered or unordered just like the array. In the ordered linked list, we can insert item so that the items are sorted and the maximum item is always at the end (pointed by head or tail). The complexity of enqueue operation is O(n) and dequeue and peek operation is O(1).

In an unordered linked list, we can insert the item at the end of the queue in constant time. The dequeue operation takes linear time (O(n)) because we need to search through the queue in order to find the item with maximum priority.

Using a binary heap

In above implementations using arrays and linked lists, one operation always takes linear time i.e. O(n). Using binary heaps, we can make all the operations faster (in logarithmic time). Please read about the binary heaps before using them in a priority queue.

Using a binary heap, the enqueue operation is insert operation in the heap. It takes O(log n) time in the worst case. Similarly, the dequeue operation is the extract-max or remove-max operation which also takes O(log n) time. The peek operation is a constant time operation. In this way, the binary heap makes the priority queue operations a way faster.

The C, C++, and Java implementation of a priority queue using the binary heap is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// C implementation of a max priority queue
#include < stdio.h >

        #define MAX_SIZE 15

// returns the index of the parent node
int parent(int i) {
        return (i - 1) / 2;
}

// return the index of the left child 
int left_child(int i) {
        return 2 * i + 1;
}

// return the index of the right child 
int right_child(int i) {
        return 2 * i + 2;
}

void swap(int * x, int * y) {
        int temp = * x;
        * x = * y;
        * y = temp;
}

// insert the item at the appropriate position
void enqueue(int a[], int data, int * n) {
        if ( * n >= MAX_SIZE) {
                printf("%s\n", "The heap is full. Cannot insert");
                return;
        }
        // first insert the time at the last position of the array 
        // and move it up
        a[ * n] = data;
        * n = * n + 1;

        // move up until the heap property satisfies
        int i = * n - 1;
        while (i != 0 && a[parent(i)] < a[i]) {
                swap( & a[parent(i)], & a[i]);
                i = parent(i);
        }
}

// moves the item at position i of array a
// into its appropriate position
void max_heapify(int a[], int i, int n) {
        // find left child node
        int left = left_child(i);

        // find right child node
        int right = right_child(i);

        // find the largest among 3 nodes
        int largest = i;

        // check if the left node is larger than the current node
        if (left <= n && a[left] > a[largest]) {
                largest = left;
        }

        // check if the right node is larger than the current node
        if (right <= n && a[right] > a[largest]) {
                largest = right;
        }

        // swap the largest node with the current node 
        // and repeat this process until the current node is larger than 
        // the right and the left node
        if (largest != i) {
                int temp = a[i];
                a[i] = a[largest];
                a[largest] = temp;
                max_heapify(a, largest, n);
        }

}

// returns the  maximum item of the heap
int get_max(int a[]) {
        return a[0];
}

// deletes the max item and return
int dequeue(int a[], int * n) {
        int max_item = a[0];

        // replace the first item with the last item
        a[0] = a[ * n - 1];
        * n = * n - 1;

        // maintain the heap property by heapifying the 
        // first item
        max_heapify(a, 0, * n);
        return max_item;
}

// prints the heap
void print_heap(int a[], int n) {
        int i;
        for (i = 0; i < n; i++) {
                printf("%d\n", a[i]);
        }
        printf("\n");
}

int main() {
        int n = 10;
        int a[MAX_SIZE];
        insert(a, 55, & n);
        insert(a, 56, & n);
        insert(a, 57, & n);
        insert(a, 58, & n);
        insert(a, 100, & n);
        print_heap(a, n);
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// C++ implementation of a priority queue

#include 
using namespace std;

class PQHeap {
private:
    const static int MAX_SIZE = 15;
    int heap[MAX_SIZE];
    int size;

public:
    PQHeap() {
        size = 0;
    }

    // returns the index of the parent node
    static int parent(int i) {
        return (i - 1) / 2;
    }

    // return the index of the left child 
    static int leftChild(int i) {
        return 2*i + 1;
    }

    // return the index of the right child 
    static int rightChild(int i) {
        return 2*i + 2;
    }


    static void swap(int *x, int *y) {
        int temp = *x;
        *x = *y;
        *y = temp;
    }

    // insert the item at the appropriate position
    void enqueue(int data) {
        if (size >= MAX_SIZE) {
            cout<<"The heap is full. Cannot insert"<<endl;
            return;
        }

        // first insert the time at the last position of the array 
        // and move it up
        heap[size] = data;
        size = size + 1;


        // move up until the heap property satisfies
        int i = size - 1;
        while (i != 0 && heap[PQHeap::parent(i)] < heap[i]) {
            PQHeap::swap(&heap[PQHeap::parent(i)], &heap[i]);
            i = PQHeap::parent(i);
        }
    }

    // moves the item at position i of array a
    // into its appropriate position
    void maxHeapify(int i){
        // find left child node
        int left = PQHeap::leftChild(i);

        // find right child node
        int right = PQHeap::rightChild(i);

        // find the largest among 3 nodes
        int largest = i;

        // check if the left node is larger than the current node
        if (left <= size && heap[left] > heap[largest]) {
            largest = left;
        }

        // check if the right node is larger than the current node 
        // and left node
        if (right <= size && heap[right] > heap[largest]) {
            largest = right;
        }

        // swap the largest node with the current node 
        // and repeat this process until the current node is larger than 
        // the right and the left node
        if (largest != i) {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }

    }

    // returns the  maximum item of the heap
    int peek() {
        return heap[0];
    }

    // deletes the max item and return
    int dequeue() {
        int maxItem = heap[0];

        // replace the first item with the last item
        heap[0] = heap[size - 1];
        size = size - 1;

        // maintain the heap property by heapifying the 
        // first item
        maxHeapify(0);
        return maxItem;
    }

    // prints the heap
    void printQueue() {
        for (int i = 0; i < size; i++) {
            cout<endl;
        }
        cout<<endl;
    }
};

int main() {
    PQHeap queue;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Java implementation of a max priority queue

class PQHeap {
    private static final int MAX_SIZE = 15;
    private int [] heap;
    private int size;

    public PQHeap() {
        heap = new int[MAX_SIZE];
        size = 0;
    }

    // returns the index of the parent node
    public static int parent(int i) {
        return (i - 1) / 2;
    }

    // return the index of the left child 
    public static int leftChild(int i) {
        return 2*i + 1;
    }

    // return the index of the right child 
    public static int rightChild(int i) {
        return 2*i + 2;
    }

    // insert the item at the appropriate position
    public void enqueue(int data) {
        if (size >= MAX_SIZE) {
            System.out.println("The queue is full. Cannot insert");
            return;
        }

        // first insert the time at the last position of the array 
        // and move it up
        heap[size] = data;
        size = size + 1;


        // move up until the heap property satisfies
        int i = size - 1;
        while (i != 0 && heap[PQHeap.parent(i)] < heap[i]) {
            int temp = heap[i];
            heap[i] = heap[parent(i)];
            heap[parent(i)] = temp;
            i = PQHeap.parent(i);
        }
    }

    // moves the item at position i of array a
    // into its appropriate position
    public void maxHeapify(int i){
        // find left child node
        int left = PQHeap.leftChild(i);

        // find right child node
        int right = PQHeap.rightChild(i);

        // find the largest among 3 nodes
        int largest = i;

        // check if the left node is larger than the current node
        if (left <= size && heap[left] > heap[largest]) {
            largest = left;
        }

        // check if the right node is larger than the current node 
        // and left node
        if (right <= size && heap[right] > heap[largest]) {
            largest = right;
        }

        // swap the largest node with the current node 
        // and repeat this process until the current node is larger than 
        // the right and the left node
        if (largest != i) {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }

    }

    // returns the  maximum item of the heap
    public int peek() {
        return heap[0];
    }

    // deletes the max item and return
    public int dequeue() {
        int maxItem = heap[0];

        // replace the first item with the last item
        heap[0] = heap[size - 1];
        size = size - 1;

        // maintain the heap property by heapifying the 
        // first item
        maxHeapify(0);
        return maxItem;
    }

    // prints the queue
    public void printQueue() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String [] args) {
        PQHeap queue = new PQHeap();
        queue.enqueue(43);
        queue.enqueue(333);
        queue.enqueue(345);
        queue.enqueue(45);
        queue.enqueue(3);
        queue.enqueue(400);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}

Complexity

The complexity of the operations of a priority queue using arrays, linked list, and the binary heap is given in the table below.

Data StructureEnQueueDeQueuePeek
Ordered ArrayO(n)O(1)O(1)
Unordered ArrayO(1)O(n)O(n)
Ordered Linked ListO(n)O(1)O(1)
Unordered Linked ListO(1)O(n)O(n)
Binary HeapO(log n)O(log n)O(1)