Priority Queue

Go back

Introduction

Priority queues are a type of container adapters, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue.

Priority queues are built on the top to the max or min heap and uses array or vector as an internal structure.

Advantages

Quickly access to the highest priority item.
Useful when trying to apply Prim's or Dijkstra's algorithm and for data compresson in Huffman code.

Disadvantages

Insertion and deletion are very slow.

Using priority queue with DTL

Initializing a priority queue

#include "priority_queue.hpp"
#include <iostream>

int main() {
  // Static
  dby::PriorityQueue<int> staMinAtTop(10, [](int a, int b){ return a < b; });
  // MAX CAPACITY = 10 elements

  // Pointer
  dby::PriorityQueue<int>* ptrMaxAtTop = new dby::PriorityQueue<int>(10);
  // MAX CAPACITY = 10 elements

  delete ptrMaxAtTop;
  return 0;
}

Priority Queue methods

max_size(): Returns the max size of the queue.
size(): Returns the number of elements in the queue.
empty(): Returns whether the queue is empty or not.
top(): Returns the topmost element of the queue.
push(T data): Adds the element 'data' at the end of the queue.
pop(): Deletes the first element of the queue.
extract(): Returns and deletes the first element of the queue.