Priority Queue Using Heap

Learn Priority Queue Using Heap 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, and the element with the highest or lowest priority is processed before other elements.

Unlike a normal queue, a priority queue does not necessarily process elements in the order they were inserted. The next element is selected according to its priority. 

Normal Queue:

A → B → C
First inserted → First processed


Priority Queue:

A (priority 2)
B (priority 10)
C (priority 5)

Processing order:

B → C → A

Why Use a Heap for a Priority Queue?

A binary heap is one of the most common ways to implement a priority queue because it provides efficient insertion and removal of the highest- or lowest-priority element.

A heap keeps the highest-priority element at the root while allowing new elements to be inserted without sorting the entire collection after every operation.

Priority Queue Operation Heap Operation Typical Time
Insert Heapify up O(log n)
Peek highest priority Read root O(1)
Remove highest priority Extract root + heapify down O(log n)
Build from existing values Build heap O(n)

Min Heap vs Max Heap Priority Queue

The type of heap determines which priority is processed first.

  • Min Heap: the smallest priority value is processed first.
  • Max Heap: the largest priority value is processed first.
Min Heap Priority Queue:

        1
       / \
      3   2

Next → priority 1


Max Heap Priority Queue:

        10
       /  \
      7    8

Next → priority 10

Priority Queue with Objects

In real applications, a priority queue usually stores more than just numbers. Each item can contain a value and a priority. 

const tasks = [
  { name: "Generate report", priority: 3 },
  { name: "Critical alert", priority: 10 },
  { name: "Send email", priority: 5 }
];

With a Max Heap, the processing order would be: 

Critical alert  → 10
Send email      → 5
Generate report  → 3

Priority Queue Insertion

When an item is inserted into a heap-based priority queue, it is first placed at the next available position in the complete binary tree.

Heapify up then moves the item toward the root if its priority requires it.

Example

Existing Max Heap:

        10
       /  \
      7    8

Insert priority 12:

        10
       /  \
      7    8
     /
    12

Since 12 has a higher priority than its parent, it moves upward. 

        12
       /  \
      10   8
     /
    7

The insertion takes O(log n) time.

Peek at the Highest Priority

The peek operation returns the highest- or lowest-priority element without removing it.

Because the root contains the extreme priority, peek takes O(1) time. 

Max Heap:

        10
       /  \
      7    8

peek() → 10

Extracting the Highest Priority

Removing the highest-priority item from a heap-based priority queue is equivalent to removing the root of the heap.

  1. Save the root item.
  2. Move the last item to the root.
  3. Remove the last array element.
  4. Heapify down from the root.
  5. Return the removed item.
Before:

        10
       /  \
      7    8
     / \
    3   5

Remove 10:

        5
       / \
      7    8
     /
    3

Heapify down:

         8
       /   \
      7     5
     /
    3

Extracting the highest-priority item takes O(log n) time.

Priority Queue Implementation in JavaScript

The following implementation uses a Max Heap. A larger priority number represents a higher priority. 

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

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

  enqueue(value, priority) {
    const item = { value, priority };

    this.heap.push(item);

    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 highestPriority = this.heap[0];

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

    let index = 0;

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

      let highest = index;

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

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

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

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

      index = highest;
    }

    return highestPriority;
  }
}

const queue = new PriorityQueue();

queue.enqueue("Generate report", 3);
queue.enqueue("Critical alert", 10);
queue.enqueue("Send email", 5);

console.log(queue.peek());
// { value: "Critical alert", priority: 10 }

console.log(queue.dequeue());
// { value: "Critical alert", priority: 10 }

console.log(queue.dequeue());
// { value: "Send email", priority: 5 }

How the Priority Queue Heap Changes

Consider inserting these tasks: 

Report   → 3
Alert    → 10
Email    → 5

After inserting all three items, a possible Max Heap is: 

        Alert(10)
        /       \
    Report(3)  Email(5)

The heap does not need to be fully sorted. It only needs to maintain the priority relationship between parents and children.

Priority Queue Is Not a Normal Queue

A normal queue follows FIFO, meaning the first item inserted is the first item removed.

A priority queue instead removes the item with the highest or lowest priority first.

Feature Normal Queue Priority Queue
Removal rule First inserted Highest or lowest priority
Typical principle FIFO Priority based
Heap required No Common implementation

Priority Queue Using an Array

A priority queue can be implemented using a normal array, but maintaining priority efficiently becomes more difficult.

For example, if the array is kept unsorted, finding the highest-priority item can require O(n) time.

If the array is kept sorted, insertion may require O(n) time because elements may need to be shifted.

A heap provides a useful balance:

  • Peek: O(1)
  • Insert: O(log n)
  • Remove highest or lowest priority: O(log n)

Priority Queue with a Min Heap

Some applications define a smaller number as a more urgent priority. In that case, a Min Heap is appropriate. 

Task A → priority 1
Task B → priority 5
Task C → priority 10

Min Heap:

        1
       / \
      5   10

Next task → Task A

The meaning of the priority value is determined by the application. The heap only needs a consistent comparison rule.

Priority Queue with a Max Heap

If larger numbers represent more important items, a Max Heap can be used. 

Task A → priority 3
Task B → priority 10
Task C → priority 5

Max Heap:

        10
       /  \
      3    5

Next task → Task B

Handling Equal Priorities

Multiple items can have the same priority. 

Task A → priority 5
Task B → priority 5
Task C → priority 10

The heap guarantees that priority 10 is processed before priority 5. It does not automatically guarantee which of Task A or Task B will be processed first.

If equal-priority items must follow insertion order, an additional sequence number can be stored with each item. 

{
  value: "Task A",
  priority: 5,
  sequence: 1
}

The comparison can then use priority first and sequence number as a tie-breaker.

Priority Queue with a Tie-Breaker

function higherPriority(a, b) {
  if (a.priority !== b.priority) {
    return a.priority > b.priority;
  }

  return a.sequence < b.sequence;
}

This allows an application to preserve insertion order among items with equal priority when that behavior is required.

Priority Queue Complexity

Operation Heap-Based Priority Queue Reason
Peek O(1) Priority item is at the root
Insert O(log n) Heapify up
Remove top priority O(log n) Extract root and heapify down
Build from n items O(n) Bottom-up heap construction
Search arbitrary item O(n) Heap is not fully sorted

Priority Queue Applications

Priority queues are useful whenever work must be processed according to importance, urgency, cost, or another ordering value.

  • CPU and task scheduling.
  • Operating system job management.
  • Network packet prioritization.
  • Event-driven systems.
  • Customer support ticket processing.
  • Emergency request handling.
  • Dijkstra's shortest path algorithm.
  • Prim's minimum spanning tree algorithm.
  • Huffman coding.
  • Top-k and streaming data problems.

Priority Queue in Dijkstra's Algorithm

Dijkstra's algorithm repeatedly needs the unprocessed vertex with the smallest known distance. A Min Heap priority queue can provide this efficiently. 

Priority Queue:

Distance 2 → Vertex B
Distance 5 → Vertex C
Distance 8 → Vertex D

Next:
Vertex B

After processing a vertex, newly discovered distances can be added to the priority queue. The smallest available distance is then processed next.

Priority Queue vs Heap

A heap is a data structure, while a priority queue is an abstract data type describing priority-based insertion and removal.

A binary heap is one common and efficient way to implement a priority queue.

Concept Meaning
Priority Queue Defines priority-based operations.
Heap Provides a structure for implementing those operations efficiently.

Common Priority Queue Mistakes

Treating It Like FIFO

A priority queue does not necessarily process items in insertion order. Priority determines which item is removed next.

Using the Wrong Heap Type

Use a Min Heap when the smallest priority value should be processed first and a Max Heap when the largest value should be processed first.

Assuming the Heap Is Fully Sorted

A heap guarantees the correct root and parent-child relationships. It does not fully sort all priority values.

Ignoring Equal Priorities

If equal-priority items need a specific ordering, add an explicit tie-breaker such as an insertion sequence number.

Searching for Arbitrary Items Efficiently

A heap is optimized for access to the highest- or lowest-priority item, not arbitrary item lookup.

Priority Queue Operation Summary

Operation Action Time
Enqueue Insert item and heapify up O(log n)
Peek Read root item O(1)
Dequeue Remove root and heapify down O(log n)
Build Create heap from existing items O(n)

Key Takeaways

  • A priority queue processes elements according to priority rather than insertion order.
  • A binary heap is a common implementation of a priority queue.
  • A Min Heap processes the smallest priority value first.
  • A Max Heap processes the largest priority value first.
  • Peek takes O(1) time.
  • Insertion takes O(log n) using heapify up.
  • Removing the highest- or lowest-priority item takes O(log n).
  • Building a heap from existing items takes O(n) with bottom-up construction.
  • Equal priorities may require a tie-breaker when ordering matters.
  • Priority queues are widely used in scheduling and graph algorithms such as Dijkstra's algorithm.

Code Examples 

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

  enqueue(value, priority) {
    const item = { value, priority };

    this.heap.push(item);

    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;
    }
  }

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

  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();

    let index = 0;

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

      let highest = index;

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

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

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

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

      index = highest;
    }

    return result;
  }
}

const queue = new PriorityQueue();

queue.enqueue("Normal task", 2);
queue.enqueue("Critical alert", 10);
queue.enqueue("Important task", 6);

console.log(queue.dequeue());
// Critical alert

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

  enqueue(value, priority) {
    const item = { value, priority };

    this.heap.push(item);

    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();

    let index = 0;

    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 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;
    }

    return result;
  }
}

const queue = new MinPriorityQueue();

queue.enqueue("Task A", 5);
queue.enqueue("Urgent task", 1);
queue.enqueue("Task B", 3);

console.log(queue.dequeue());
// Urgent task

console.log(queue.dequeue());
// Task B
    
class PriorityQueue {
  constructor() {
    this.heap = [];
    this.sequence = 0;
  }

  isHigherPriority(a, b) {
    if (a.priority !== b.priority) {
      return a.priority > b.priority;
    }

    return a.sequence < b.sequence;
  }

  enqueue(value, priority) {
    const item = {
      value,
      priority,
      sequence: this.sequence++
    };

    this.heap.push(item);

    let index = this.heap.length - 1;

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

      if (
        this.isHigherPriority(
          this.heap[parent],
          this.heap[index]
        )
      ) {
        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();

    let index = 0;

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

      let highest = index;

      if (
        left < this.heap.length &&
        this.isHigherPriority(
          this.heap[left],
          this.heap[highest]
        )
      ) {
        highest = left;
      }

      if (
        right < this.heap.length &&
        this.isHigherPriority(
          this.heap[right],
          this.heap[highest]
        )
      ) {
        highest = right;
      }

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

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

      index = highest;
    }

    return result;
  }
}

const queue = new PriorityQueue();

queue.enqueue("Task A", 5);
queue.enqueue("Task B", 5);
queue.enqueue("Critical task", 10);

console.log(queue.dequeue());
// Critical task

console.log(queue.dequeue());
// Task A

Pro Tip

Think of a heap-based priority queue as a system that keeps only the most important item immediately accessible. Use a Min Heap for the smallest priority value first and a Max Heap for the largest priority value first.

🎨 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.