Priority Queues Data Structure

This chapter is also already explained in this post. So if you already have prior knowledge, you can skip this chapter.

Priority queue is a type of queue in which every element has a key associated to it and the queue returns the element according to these keys, unlike the traditional queue which works on first come first serve basis.

Thus, a max-priority queue returns the element with the maximum key first whereas, a min-priority queue returns the element with the smallest key first.

priority queue

Priority queues are used in many algorithms like Huffman Codes, Prim's algorithm, etc. It is also used in scheduling processes for a computer, etc.

Heaps are great for implementing a priority queue because of the largest and the smallest element at the root of the tree for a max-heap and a min-heap respectively. We use a max-heap for a max-priority queue and a min-heap for a min-priority queue.

There are mainly 4 operations we want from a priority queue:

1. Insert → To insert a new element in the queue.

2. Maximum/Minimum → To get the maximum and the minimum element from the max-priority queue and min-priority queue respectively.

3. Extract Maximum/Minimum → To remove and return the maximum and the minimum element from the max-priority queue and min-priority queue respectively.

4. Increase/Decrease key → To increase or decrease the key of any element in the queue.

A priority queue stores its data in a specific order according to the keys of the elements. So, inserting a new data must go in a place according to the specified order. This is what the insert operation does.

The entire point of priority queue is to get the data according to the key of the data and the Maximum/Minimum and Extract Maximum/Minimum operation do this for us.

With these operations, we have fulfilled most of our demand for a priority queue i.e., to insert data into the queue and take data from the queue. But we may also face a situation in which we need to change the key of an element, so the Increase/Decrease key operation is used to do that.

Let's learn to code these operations to make a priority queue.

As stated earlier, we are going to use a heap for the priority queue.

Maximum/Minimum

We know that the maximum (or minimum) element of a priority queue is at the root of the max-heap (or min-heap). So, we just need to return the element at the root of the heap.

heap

MAXIMUM(A)
return A[1]

Returning an element from an array is a constant time taking process, so it is a $\Theta(1)$ process.

Extract Maximum/Minimum

This is like the pop operation of a queue, we return the maximum (or minimum) element as well as delete it from the heap. So, we have to return and delete the root of a heap. Firstly, we store the value of the root in a variable to return it later from the function and then we just make the root equal to the last element of the heap. Now that the root is equal to the last element of the heap, we delete the last element easily and reduce the size of the heap by 1.

Dequeue from priority queue

Doing this, we have disturbed the heap property of the root but we have not touched any of its children, so they are still heaps. So, we can call Heapify on the root to make the tree a heap again.

EXTRACT-MAXIMUM(A)
max = A[1] // storing maximum value
A[1] = A[heap_size] // making root equal to the last element
heap_size = heap_size-1 // delete last element
MAX-HEAPIFY(A, 1) // root is not following max-heap property
return max //returning the maximum value

All the steps are constant time taking processes except the Heapify operation, it will take $O(\lg{n})$ time and thus the Extract Maximum/Minimum is going to take $O(\lg{n})$ time.

Increase/Decrease key

Whenever we change the key of an element, we must change its position to go in a place of correct order according to the new key. If the heap is a max-heap and we are decreasing the key, then we just need to check if the key became smaller than any of its children or not. If the new key is smaller than any of its children, then it is violating the heap property. In that case, we will call Heapify on it.

priority queue

In the case of increasing the key of an element in a max-heap, we might make it greater than the key of its parent and thus violating the heap property. In this case, we swap the values of the parent and the node and this is done until the parent of the node becomes greater than the node itself.

chaning key in priority queue

In the case of a min-queue, we do exactly the opposite of the above steps.

INCREASE-KEY(A, i, key)
A[i] = key // changing key
while i > 1 and A[Parent(i)] < A[i] // if parent is less than A[i], we will swap.
  swap (A[i], A[Parent(i)])
  i = Parent(i)

To decrease a key, we can simply change the key and call Heapify on it.

DECREASE-KEY(A, i, key)
A[i] = key // changing key
MAX-HEAPIFY(A, i)

It is similar to the Heapify operation. Instead of traveling down the tree, we are traveling up, and so it is also going to take $\lg{n}$ time in the worst case i.e., it is an $O(\lg{n})$ operation.

Insert

The insert operation inserts a new element in the correct order according to its key. We just insert a new element at the last of the heap and increase the heap size by 1. Since it is the last element, so we first give a very large value (infinity) in the case of min-heap and a very less value (-infinity) in the case of max-heap. Then we just change the key of the element by using the Increase/Decrease key operation.

INSERT(A, key)
heap_size = heap_size+1 // increasing heap size by 1
A[heap_size] = -infinity // making last element very less
INCREASE-KEY(A, heap_size, key) // chaning key of last element

All the steps are constant time taking steps, except the Increase/Decrease key. So it will also take $O(\lg{n})$ time.

Code for Max-Priority Queue - C, Java and Python

C
Python
Java

#include <stdio.h>

int tree_array_size = 20;
int heap_size = 0;
const int INF = 100000;

void swap( int *a, int *b ) {
int t;
t = *a;
*a = *b;
*b = t;
}

//function to get right child of a node of a tree
int get_right_child(int A[], int index) {
if((((2*index)+1) < tree_array_size) && (index >= 1))
  return (2*index)+1;
return -1;
}

//function to get left child of a node of a tree
int get_left_child(int A[], int index) {
  if(((2*index) < tree_array_size) && (index >= 1))
      return 2*index;
  return -1;
}

//function to get the parent of a node of a tree
int get_parent(int A[], int index) {
if ((index > 1) && (index < tree_array_size)) {
  return index/2;
}
return -1;
}

void max_heapify(int A[], int index) {
int left_child_index = get_left_child(A, index);
int right_child_index = get_right_child(A, index);

// finding largest among index, left child and right child
int largest = index;

if ((left_child_index <= heap_size) && (left_child_index>0)) {
  if (A[left_child_index] > A[largest]) {
    largest = left_child_index;
  }
}

if ((right_child_index <= heap_size && (right_child_index>0))) {
  if (A[right_child_index] > A[largest]) {
    largest = right_child_index;
  }
}

// largest is not the node, node is not a heap
if (largest != index) {
  swap(&A[index], &A[largest]);
  max_heapify(A, largest);
}
}

void build_max_heap(int A[]) {
int i;
for(i=heap_size/2; i>=1; i--) {
  max_heapify(A, i);
}
}

int maximum(int A[]) {
return A[1];
}

int extract_max(int A[]) {
int maxm = A[1];
A[1] = A[heap_size];
heap_size--;
max_heapify(A, 1);
return maxm;
}

void increase_key(int A[], int index, int key) {
A[index] = key;
while((index>1) && (A[get_parent(A, index)] < A[index])) {
  swap(&A[index], &A[get_parent(A, index)]);
  index = get_parent(A, index);
}
}

void decrease_key(int A[], int index, int key) {
A[index] = key;
max_heapify(A, index);
}

void insert(int A[], int key) {
heap_size++;
A[heap_size] = -1*INF;
increase_key(A, heap_size, key);
}

void print_heap(int A[]) {
int i;
for(i=1; i<=heap_size; i++) {
  printf("%d\n",A[i]);
}
printf("\n");
}

int main() {
int A[tree_array_size];
insert(A, 20);
insert(A, 15);
insert(A, 8);
insert(A, 10);
insert(A, 5);
insert(A, 7);
insert(A, 6);
insert(A, 2);
insert(A, 9);
insert(A, 1);

print_heap(A);

increase_key(A, 5, 22);
print_heap(A);

decrease_key(A, 1, 13);
print_heap(A);

printf("%d\n\n", maximum(A));
printf("%d\n\n", extract_max(A));

print_heap(A);

printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
printf("%d\n", extract_max(A));
return 0;
}

heap_size = 0
tree_array_size = 20
INF = 100000

# function to get right child of a node of a tree
def get_right_child(A, index):
if((((2*index)+1) < len(A)) and (index >= 1)):
  return (2*index)+1
return -1

# function to get left child of a node of a tree
def get_left_child(A, index):
  if(((2*index) < len(A)) and (index >= 1)):
      return 2*index
  return -1

# function to get the parent of a node of a tree
def get_parent(A, index):
if ((index > 1) and (index < len(A))):
  return index//2
return -1

def max_heapify(A, index):
left_child_index = get_left_child(A, index)
right_child_index = get_right_child(A, index)

# finding largest among index, left child and right child
largest = index

if ((left_child_index <= heap_size) and (left_child_index>0)):
  if (A[left_child_index] > A[largest]):
    largest = left_child_index

if ((right_child_index <= heap_size and (right_child_index>0))):
  if (A[right_child_index] > A[largest]):
    largest = right_child_index

# largest is not the node, node is not a heap
if (largest != index):
  A[index], A[largest] = A[largest], A[index]
  max_heapify(A, largest)

def build_max_heap(A):
for i in range(heap_size//2, 0, -1):
  max_heapify(A, i)

def maximum(A):
return A[1]

def extract_max(A):
global heap_size
minm = A[1]
A[1] = A[heap_size]
heap_size = heap_size-1
max_heapify(A, 1)
return minm

def increase_key(A, index, key):
A[index] = key
while((index>1) and (A[get_parent(A, index)] < A[index])):
  A[index], A[get_parent(A, index)] = A[get_parent(A, index)], A[index]
  index = get_parent(A, index)

def decrease_key(A, index, key):
A[index] = key
max_heapify(A, index)

def insert(A , key):
global heap_size
heap_size = heap_size+1
A[heap_size] = -1*INF
increase_key(A, heap_size, key)

if __name__ == '__main__':
A = [None]*tree_array_size

insert(A, 20)
insert(A, 15)
insert(A, 8)
insert(A, 10)
insert(A, 5)
insert(A, 7)
insert(A, 6)
insert(A, 2)
insert(A, 9)
insert(A, 1)

print(A[1:heap_size+1])

increase_key(A, 5, 22)
print(A[1:heap_size+1])

print(maximum(A))
print(extract_max(A))

print(A[1:heap_size+1])

print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))
print(extract_max(A))

class MaximumPriorityQueue {
public static int heapSize = 0;
public static int treeArraySize = 20;
public static int INF = 100000;

//function to get right child of a node of a tree
public static int getRightChild(int A[], int index) {
  if((((2*index)+1) < A.length && (index >= 1)))
    return (2*index)+1;
  return -1;
}

//function to get left child of a node of a tree
public static int getLeftChild(int A[], int index) {
    if(((2*index) < A.length && (index >= 1)))
        return 2*index;
    return -1;
}

//function to get the parent of a node of a tree
public static int getParent(int A[], int index) {
  if ((index > 1) && (index < A.length)) {
    return index/2;
  }
  return -1;
}

public static void maxHeapify(int A[], int index) {
  int leftChildIndex = getLeftChild(A, index);
  int rightChildIndex = getRightChild(A, index);

  // finding largest among index, left child and right child
  int largest = index;

  if ((leftChildIndex <= heapSize) && (leftChildIndex>0)) {
    if (A[leftChildIndex] > A[largest]) {
      largest = leftChildIndex;
    }
  }

  if ((rightChildIndex <= heapSize && (rightChildIndex>0))) {
    if (A[rightChildIndex] > A[largest]) {
      largest = rightChildIndex;
    }
  }

  // largest is not the node, node is not a heap
  if (largest != index) {
    int temp;
    //swapping
    temp = A[largest];
    A[largest] = A[index];
    A[index] = temp;
    maxHeapify(A, largest);
  }
}

public static void buildMaxHeap(int A[]) {
  for(int i=heapSize/2; i>=1; i--) {
    maxHeapify(A, i);
  }
}

public static int maximum(int A[]) {
  return A[1];
}

public static int extractMax(int A[]) {
  int maxm = A[1];
  A[1] = A[heapSize];
  heapSize--;
  maxHeapify(A, 1);
  return maxm;
}

public static void increaseKey(int A[], int index, int key) {
  A[index] = key;
  while((index>1) && (A[getParent(A, index)] < A[index])) {
    int temp;
    temp = A[getParent(A, index)];
    A[getParent(A, index)] = A[index];
    A[index] = temp;
    index = getParent(A, index);
  }
}

public static void decreaseKey(int A[], int index, int key) {
  A[index] = key;
  maxHeapify(A, index);
}

public static void insert(int A[], int key) {
  heapSize++;
  A[heapSize] = -1*INF;
  increaseKey(A, heapSize, key);
}

public static void printHeap(int A[]) {
  for(int i=1; i<=heapSize; i++) {
    System.out.println(A[i]);
  }
  System.out.println("");
}

public static void main(String[] args) {
  int A[] = new int[treeArraySize];
  buildMaxHeap(A);

  insert(A, 20);
  insert(A, 15);
  insert(A, 8);
  insert(A, 10);
  insert(A, 5);
  insert(A, 7);
  insert(A, 6);
  insert(A, 2);
  insert(A, 9);
  insert(A, 1);

  printHeap(A);

  increaseKey(A, 5, 22);
  printHeap(A);

  decreaseKey(A, 1, 13);
  printHeap(A);

  System.out.println(maximum(A));
  System.out.println("");
  System.out.println(extractMax(A));
  System.out.println("");

  printHeap(A);

  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
  System.out.println(extractMax(A));
}
}

Code for Min-Priority Queue - C, Java and Python

C
Python
Java

#include <stdio.h>

int tree_array_size = 20;
int heap_size = 0;
const int INF = 100000;

void swap( int *a, int *b ) {
int t;
t = *a;
*a = *b;
*b = t;
}

//function to get right child of a node of a tree
int get_right_child(int A[], int index) {
if((((2*index)+1) < tree_array_size) && (index >= 1))
  return (2*index)+1;
return -1;
}

//function to get left child of a node of a tree
int get_left_child(int A[], int index) {
  if(((2*index) < tree_array_size) && (index >= 1))
      return 2*index;
  return -1;
}

//function to get the parent of a node of a tree
int get_parent(int A[], int index) {
if ((index > 1) && (index < tree_array_size)) {
  return index/2;
}
return -1;
}

void min_heapify(int A[], int index) {
int left_child_index = get_left_child(A, index);
int right_child_index = get_right_child(A, index);

// finding smallest among index, left child and right child
int smallest = index;

if ((left_child_index <= heap_size) && (left_child_index>0)) {
  if (A[left_child_index] < A[smallest]) {
    smallest = left_child_index;
  }
}

if ((right_child_index <= heap_size && (right_child_index>0))) {
  if (A[right_child_index] < A[smallest]) {
    smallest = right_child_index;
  }
}

// smallest is not the node, node is not a heap
if (smallest != index) {
  swap(&A[index], &A[smallest]);
  min_heapify(A, smallest);
}
}

void build_min_heap(int A[]) {
int i;
for(i=heap_size/2; i>=1; i--) {
  min_heapify(A, i);
}
}

int minimum(int A[]) {
return A[1];
}

int extract_min(int A[]) {
int minm = A[1];
A[1] = A[heap_size];
heap_size--;
min_heapify(A, 1);
return minm;
}

void decrease_key(int A[], int index, int key) {
A[index] = key;
while((index>1) && (A[get_parent(A, index)] > A[index])) {
  swap(&A[index], &A[get_parent(A, index)]);
  index = get_parent(A, index);
}
}

void increase_key(int A[], int index, int key) {
A[index] = key;
min_heapify(A, index);
}

void insert(int A[], int key) {
heap_size++;
A[heap_size] = INF;
decrease_key(A, heap_size, key);
}

void print_heap(int A[]) {
int i;
for(i=1; i<=heap_size; i++) {
  printf("%d\n",A[i]);
}
printf("\n");
}

int main() {
int A[tree_array_size];
insert(A, 20);
insert(A, 15);
insert(A, 8);
insert(A, 10);
insert(A, 5);
insert(A, 7);
insert(A, 6);
insert(A, 2);
insert(A, 9);
insert(A, 1);

print_heap(A);

increase_key(A, 5, 22);
print_heap(A);

printf("%d\n\n", minimum(A));
printf("%d\n\n", extract_min(A));

print_heap(A);

printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
printf("%d\n", extract_min(A));
return 0;
}

heap_size = 0
tree_array_size = 20
INF = 100000

# function to get right child of a node of a tree
def get_right_child(A, index):
if((((2*index)+1) < len(A)) and (index >= 1)):
  return (2*index)+1
return -1

# function to get left child of a node of a tree
def get_left_child(A, index):
  if(((2*index) < len(A)) and (index >= 1)):
      return 2*index
  return -1

# function to get the parent of a node of a tree
def get_parent(A, index):
if ((index > 1) and (index < len(A))):
  return index//2
return -1

def min_heapify(A, index):
left_child_index = get_left_child(A, index)
right_child_index = get_right_child(A, index)

# finding smallest among index, left child and right child
smallest = index

if ((left_child_index <= heap_size) and (left_child_index>0)):
  if (A[left_child_index] < A[smallest]):
    smallest = left_child_index

if ((right_child_index <= heap_size and (right_child_index>0))):
  if (A[right_child_index] < A[smallest]):
    smallest = right_child_index

# smallest is not the node, node is not a heap
if (smallest != index):
  A[index], A[smallest] = A[smallest], A[index]
  min_heapify(A, smallest)

def build_min_heap(A):
for i in range(heap_size//2, 0, -1):
  min_heapify(A, i)

def minimum(A):
return A[1]

def extract_min(A):
global heap_size
minm = A[1]
A[1] = A[heap_size]
heap_size = heap_size-1
min_heapify(A, 1)
return minm

def decrease_key(A, index, key):
A[index] = key
while((index>1) and (A[get_parent(A, index)] > A[index])):
  A[index], A[get_parent(A, index)] = A[get_parent(A, index)], A[index]
  index = get_parent(A, index)

def increase_key(A, index, key):
A[index] = key
min_heapify(A, index)

def insert(A , key):
global heap_size
heap_size = heap_size+1
A[heap_size] = INF
decrease_key(A, heap_size, key)

if __name__ == '__main__':
# tree is starting from index 1 and not 0
A = [0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7]

insert(A, 20)
insert(A, 15)
insert(A, 8)
insert(A, 10)
insert(A, 5)
insert(A, 7)
insert(A, 6)
insert(A, 2)
insert(A, 9)
insert(A, 1)

print(A[1:heap_size+1])

increase_key(A, 5, 22)
print(A[1:heap_size+1])

decrease_key(A, 1, 13)
print(A[1:heap_size+1])

print(minimum(A))
print(extract_min(A))

print(A[1:heap_size+1])

print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))
print(extract_min(A))

class MinimumPriorityQueue {
public static int heapSize = 0;
public static int treeArraySize = 20;
public static int INF = 100000;

//function to get right child of a node of a tree
public static int getRightChild(int A[], int index) {
  if((((2*index)+1) < A.length && (index >= 1)))
    return (2*index)+1;
  return -1;
}

//function to get left child of a node of a tree
public static int getLeftChild(int A[], int index) {
    if(((2*index) < A.length && (index >= 1)))
        return 2*index;
    return -1;
}

//function to get the parent of a node of a tree
public static int getParent(int A[], int index) {
  if ((index > 1) && (index < A.length)) {
    return index/2;
  }
  return -1;
}

public static void minHeapify(int A[], int index) {
  int leftChildIndex = getLeftChild(A, index);
  int rightChildIndex = getRightChild(A, index);

  // finding smallest among index, left child and right child
  int smallest = index;

  if ((leftChildIndex <= heapSize) && (leftChildIndex>0)) {
    if (A[leftChildIndex] < A[smallest]) {
      smallest = leftChildIndex;
    }
  }

  if ((rightChildIndex <= heapSize && (rightChildIndex>0))) {
    if (A[rightChildIndex] < A[smallest]) {
      smallest = rightChildIndex;
    }
  }

  // smallest is not the node, node is not a heap
  if (smallest != index) {
    int temp;
    //swapping
    temp = A[smallest];
    A[smallest] = A[index];
    A[index] = temp;
    minHeapify(A, smallest);
  }
}

public static void buildMinHeap(int A[]) {
  for(int i=heapSize/2; i>=1; i--) {
    minHeapify(A, i);
  }
}

public static int minimum(int A[]) {
  return A[1];
}

public static int extractMin(int A[]) {
  int minm = A[1];
  A[1] = A[heapSize];
  heapSize--;
  minHeapify(A, 1);
  return minm;
}

public static void decreaseKey(int A[], int index, int key) {
  A[index] = key;
  while((index>1) && (A[getParent(A, index)] > A[index])) {
    int temp;
    temp = A[getParent(A, index)];
    A[getParent(A, index)] = A[index];
    A[index] = temp;
    index = getParent(A, index);
  }
}

public static void increaseKey(int A[], int index, int key) {
  A[index] = key;
  minHeapify(A, index);
}

public static void insert(int A[], int key) {
  heapSize++;
  A[heapSize] = INF;
  decreaseKey(A, heapSize, key);
}

public static void printHeap(int A[]) {
  for(int i=1; i<=heapSize; i++) {
    System.out.println(A[i]);
  }
  System.out.println("");
}

public static void main(String[] args) {
  int A[] = new int[treeArraySize];
  buildMinHeap(A);

  insert(A, 20);
  insert(A, 15);
  insert(A, 8);
  insert(A, 10);
  insert(A, 5);
  insert(A, 7);
  insert(A, 6);
  insert(A, 2);
  insert(A, 9);
  insert(A, 1);

  printHeap(A);

  increaseKey(A, 5, 22);
  printHeap(A);

  System.out.println(minimum(A));
  System.out.println("");
  System.out.println(extractMin(A));
  System.out.println("");

  printHeap(A);

  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
  System.out.println(extractMin(A));
}
}

Time is a drug. Too much of it kills you

- Terry Pratchett