Priority Queue Data Structure

Learn Priority Queue Data Structure with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Priority Queue?

A priority queue is a data structure in which each element is associated with a priority. Instead of always processing elements in the order they were inserted, the element with the highest priority is processed first.

A priority queue is different from a standard queue. A normal queue follows FIFO (First In, First Out), while a priority queue removes elements according to their priority. If two elements have the same priority, their insertion order may be used as a tie-breaker depending on the implementation.

Example: Consider a hospital emergency department. A patient with a critical condition may need treatment before a patient with a minor condition, even if the minor-condition patient arrived first. A priority queue can model this behavior.

Priority Queue vs Regular Queue

The key difference is how the next element is selected. A regular queue considers arrival order, while a priority queue considers priority.

Feature Regular Queue Priority Queue
Ordering Insertion order Priority
Removal Front element Highest or lowest priority element
Typical rule FIFO Priority-based
Common implementation Array or linked list Heap

How Priority Works

A priority queue needs a rule for comparing priorities. Depending on the application, either the smallest value or the largest value can represent the highest priority.

  • Min-priority queue: the element with the smallest priority value is removed first.
  • Max-priority queue: the element with the largest priority value is removed first.

For example, if priorities are represented as numbers and smaller numbers mean more urgent work, priorities 1, 2, 3 would be processed in that order.

Core Priority Queue Operations

Most priority queue implementations provide a small set of fundamental operations.

Operation Purpose
enqueue / insert Adds an element with a priority
dequeue / extract Removes the highest-priority element
peek Views the highest-priority element without removing it
isEmpty Checks whether the queue contains elements
size Returns the number of stored elements

Priority Queue Using an Array

A priority queue can be implemented with a simple array. Each element can contain a value and its priority. The simplest approach is to search for the highest-priority element whenever a removal is requested. 

const queue = [
  { value: "Email customer", priority: 2 },
  { value: "Fix production bug", priority: 1 },
  { value: "Update documentation", priority: 3 }
];

// Smaller number means higher priority
const nextTask = queue.reduce((best, current) =>
  current.priority < best.priority ? current : best
);

console.log(nextTask);

This approach is easy to understand, but finding the highest-priority element requires scanning the array. For large collections, a heap-based implementation is usually more efficient.

Priority Queue Using a Heap

A heap is one of the most common data structures used to implement a priority queue. A min-heap keeps the smallest priority at the root, while a max-heap keeps the largest priority at the root.

Because the highest-priority element is kept at the root, a heap allows the next element to be accessed efficiently without scanning every element.

Important: A priority queue is an abstract data structure or behavior. A heap is one implementation technique used to provide that behavior efficiently.

Min-Priority Queue Example

In a min-priority queue, the smaller priority value represents greater importance. The following example uses a binary heap to maintain the smallest priority at the root. 

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[parentIndex].priority <= this.heap[index].priority) {
        break;
      }

      [this.heap[parentIndex], this.heap[index]] =
        [this.heap[index], this.heap[parentIndex]];

      index = parentIndex;
    }
  }

  dequeue() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const result = this.heap[0];
    this.heap[0] = this.heap.pop();

    this.bubbleDown();

    return result;
  }

  bubbleDown() {
    let index = 0;

    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let smallest = index;

      if (
        left < this.heap.length &&
        this.heap[left].priority < this.heap[smallest].priority
      ) {
        smallest = left;
      }

      if (
        right < this.heap.length &&
        this.heap[right].priority < this.heap[smallest].priority
      ) {
        smallest = right;
      }

      if (smallest === index) {
        break;
      }

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }

  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

const queue = new PriorityQueue();

queue.enqueue("Normal task", 3);
queue.enqueue("Critical task", 1);
queue.enqueue("Important task", 2);

console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());

How Heap-Based Priority Queue Works

When an element is inserted into a heap-based priority queue, it is initially placed at the end of the heap. The element then moves upward until the heap property is restored. This operation is called bubble up or sift up.

When the highest-priority element is removed, the last element is moved to the root. The heap then rearranges itself by moving that element downward. This operation is called bubble down, sift down, or heapify down.

  1. Insert the new element at the end of the heap.
  2. Compare it with its parent.
  3. Move it upward while the priority rule is violated.
  4. For removal, take the root element.
  5. Move the final element to the root.
  6. Move it downward until the heap property is restored.

Priority Queue Complexity

The performance of a priority queue depends on how it is implemented. A heap provides a useful balance between insertion and removal performance.

Operation Heap-Based Priority Queue
Peek O(1)
Insert O(log n)
Remove highest priority O(log n)
Search for arbitrary value O(n)

Min-Priority Queue and Max-Priority Queue

The choice between a min-priority queue and a max-priority queue depends on what the application considers the most important element.

Min-Priority Queue

The smallest priority value is processed first. It is commonly useful when lower values represent earlier deadlines, shorter distances, or greater urgency.

Max-Priority Queue

The largest priority value is processed first. It is useful when larger values represent greater importance, score, or urgency.

Where Priority Queues Are Used

Priority queues are useful whenever work must be processed according to importance, cost, distance, urgency, or another ordering rule rather than simple arrival time.

  • Operating systems: scheduling processes or tasks based on priority.
  • Network systems: handling packets or requests with different priorities.
  • Shortest-path algorithms: selecting the next node with the smallest known distance.
  • Task scheduling: processing urgent jobs before lower-priority jobs.
  • Event simulation: processing events according to their scheduled time.
  • Load balancing: selecting work according to cost or importance.
  • Graph algorithms: supporting algorithms such as Dijkstra's algorithm and Prim's algorithm.

Priority Queue in Dijkstra's Algorithm

A particularly important use of a priority queue is Dijkstra's shortest-path algorithm. The algorithm repeatedly needs to select the unprocessed vertex with the smallest known distance.

A min-priority queue can efficiently provide the vertex with the smallest distance. After discovering a shorter path, the updated distance can be inserted into the priority queue for future processing. 

const queue = new PriorityQueue();

queue.enqueue("A", 0);
queue.enqueue("B", 8);
queue.enqueue("C", 3);

const next = queue.dequeue();

console.log(next);
// { value: "A", priority: 0 }

This pattern allows an algorithm to repeatedly retrieve the currently most important candidate without scanning the entire collection each time.

Priority Queue Does Not Fully Sort Its Elements

A common misconception is that a priority queue keeps every element completely sorted. A heap does not generally maintain a fully sorted sequence. It only maintains enough ordering to guarantee that the highest-priority element is available at the root.

For example, a min-heap guarantees that the smallest element is at the root, but the remaining elements do not need to appear in ascending order.

If you need all elements in sorted order, a sorting algorithm may be more appropriate. If you repeatedly need the next highest-priority element while elements are being added and removed, a priority queue is often a better fit.

Priority Queue With Equal Priorities

Multiple elements can have the same priority. The application must decide how ties should be handled. Some systems preserve insertion order for equal priorities, while simpler implementations only guarantee that the priority condition is satisfied. 

const tasks = [
  { name: "Task A", priority: 1 },
  { name: "Task B", priority: 2 },
  { name: "Task C", priority: 1 }
];

// Both Task A and Task C have the same priority.
// A production implementation can use an additional
// sequence number when stable ordering is required.

Common Priority Queue Mistakes

  • Assuming a priority queue always follows FIFO ordering.
  • Confusing a priority queue with a fully sorted array.
  • Using an unsorted array when frequent insertions and removals require better performance.
  • Forgetting whether smaller or larger values represent higher priority.
  • Removing an element without restoring the heap property.
  • Ignoring how equal-priority elements should be handled.
  • Searching a heap as though it were a binary search tree.

Choosing the Right Implementation

The implementation should match the workload. A simple array may be sufficient for a small collection or an educational example, while a binary heap is generally more appropriate when priority operations occur frequently.

Implementation Useful When
Unsorted array Simple implementation and infrequent removals
Sorted array Fast access to the next priority element with more expensive insertion
Binary heap Frequent insertion and removal operations
Specialized heap Advanced workloads with specific performance requirements

Priority Queue and Heap: The Key Relationship

Understanding the relationship between these two concepts is important when learning data structures. A priority queue describes how elements should be accessed and removed based on priority. A heap is a data structure that can efficiently implement those requirements.

This distinction is useful in interviews and real-world development because different implementations can provide priority queue behavior. The heap is popular because it provides efficient insertion, removal, and access to the highest-priority element.

Key Takeaways

  • A priority queue processes elements according to priority rather than insertion order.
  • A min-priority queue removes the smallest priority value first.
  • A max-priority queue removes the largest priority value first.
  • Priority queues commonly support insertion, removal, peek, size, and empty checks.
  • Binary heaps are a common efficient implementation of priority queues.
  • Heap-based insertion and removal generally take O(log n) time.
  • Peeking at the highest-priority element takes O(1) time in a binary heap.
  • Priority queues are widely used in scheduling and graph algorithms.

Code Examples 

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(value, priority) {
    this.items.push({ value, priority });
  }

  dequeue() {
    if (this.items.length === 0) {
      return null;
    }

    let bestIndex = 0;

    for (let i = 1; i < this.items.length; i++) {
      if (this.items[i].priority < this.items[bestIndex].priority) {
        bestIndex = i;
      }
    }

    return this.items.splice(bestIndex, 1)[0];
  }

  peek() {
    if (this.items.length === 0) {
      return null;
    }

    let bestIndex = 0;

    for (let i = 1; i < this.items.length; i++) {
      if (this.items[i].priority < this.items[bestIndex].priority) {
        bestIndex = i;
      }
    }

    return this.items[bestIndex];
  }
}

const queue = new PriorityQueue();

queue.enqueue("Normal task", 3);
queue.enqueue("Critical task", 1);
queue.enqueue("Important task", 2);

console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());
    
class MinPriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);

      if (this.heap[parent].priority <= this.heap[index].priority) {
        break;
      }

      [this.heap[parent], this.heap[index]] =
        [this.heap[index], this.heap[parent]];

      index = parent;
    }
  }

  dequeue() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const result = this.heap[0];
    this.heap[0] = this.heap.pop();

    this.bubbleDown();

    return result;
  }

  bubbleDown() {
    let index = 0;

    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let smallest = index;

      if (
        left < this.heap.length &&
        this.heap[left].priority < this.heap[smallest].priority
      ) {
        smallest = left;
      }

      if (
        right < this.heap.length &&
        this.heap[right].priority < this.heap[smallest].priority
      ) {
        smallest = right;
      }

      if (smallest === index) {
        break;
      }

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }

  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }
}

const queue = new MinPriorityQueue();

queue.enqueue("Backup database", 3);
queue.enqueue("Fix critical bug", 1);
queue.enqueue("Send report", 2);

console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
    
const tasks = [
  { name: "Generate report", priority: 3 },
  { name: "Fix production issue", priority: 1 },
  { name: "Review pull request", priority: 2 },
  { name: "Update documentation", priority: 4 }
];

while (tasks.length > 0) {
  let highestPriorityIndex = 0;

  for (let i = 1; i < tasks.length; i++) {
    if (tasks[i].priority < tasks[highestPriorityIndex].priority) {
      highestPriorityIndex = i;
    }
  }

  const task = tasks.splice(highestPriorityIndex, 1)[0];

  console.log(
    `Processing: ${task.name} (Priority: ${task.priority})`
  );
}

Pro Tip

When implementing a priority queue, first decide whether smaller or larger values represent higher priority. For frequent insertions and removals, a binary heap is usually more suitable than repeatedly scanning or sorting an array.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.