Heap Tree as Priority Queue: Complete Guide with Real-Life Examples and Implementation

Heap Tree as Priority Queue

Data structures are the backbone of computer science and software engineering. Among them, the Priority Queue is one of the most powerful and widely used structures in modern computing systems. Unlike a normal queue where the first inserted element is removed first (FIFO), a priority queue removes elements based on their priority level.

One of the most efficient ways to implement a priority queue is by using a Heap Tree.

This lab activity focuses on understanding Heap Tree as a Priority Queue, implementing it using both array-based and dynamic approaches, and applying it to solve real-world problems.

Introduction to Priority Queue

A Priority Queue is a special type of queue where each element has an associated priority.

The element with the highest priority is removed before others.

Example Scenario

Imagine a hospital emergency room.

Patients are not treated in the order they arrive.

Instead:

• Critical patients are treated first
• Serious patients next
• Minor injuries later

This is exactly how a Priority Queue works.

For details, you visit below link:

Lesson 21: Heap Data Structure Explained with Max Heap, Min Heap, Insertion, Deletion & Priority Queue

Why Use Heap Tree for Priority Queue?

Heap Trees provide:

✅ Fast insertion
✅ Fast deletion
✅ Efficient memory usage
✅ Automatic sorting by priority

Lab Objectives

This lab helps students gain practical understanding of Priority Queues.

Objective 1: Design Priority Queue Array Based

Implement a priority queue using arrays.

Concept

A heap can be stored inside an array.

For index i:

• Parent = (i – 1) / 2
• Left Child = 2i + 1
• Right Child = 2i + 2

Array Representation Example

Heap:

    50
/         \
30       40
/ \       /
10 20 35

Stored as:

[50, 30, 40, 10, 20, 35]

Array-Based Priority Queue Implementation in C++

#include <iostream>
using namespace std;

class PriorityQueue {
    private:
    int heap[100];
    int size;

    public:
    PriorityQueue() {
        size = 0;
    }

    void insert(int value) {
        int i = size;
        heap[size++] = value;

        while(i != 0 && heap[(i - 1) / 2] < heap[i]) {
            swap(heap[i], heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    void deleteMax() {
        if(size <= 0) return;

        heap[0] = heap[size - 1];
        size--;

        int i = 0;

        while(true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;

            if(left < size && heap[left] > heap[largest])
                largest = left;

            if(right < size && heap[right] > heap[largest])
                largest = right;

            if(largest != i) {
                swap(heap[i], heap[largest]);
                i = largest;
            } else {
                break;
            }
        }
    }

    void display() {
        for(int i = 0; i < size; i++)
            cout << heap[i] << " ";
        cout << endl;
    }
};

int main() {
    PriorityQueue pq;

    pq.insert(50);
    pq.insert(30);
    pq.insert(40);
    pq.insert(70);

    pq.display();

    pq.deleteMax();
    pq.display();

    return 0;
}

Deletion

When deleting:

1. Remove root
2. Move last element to root
3. Compare with children
4. Swap downward

This process is called:

Heapify Down

Objective 2: Design Priority Queue Dynamic

Dynamic priority queues use memory allocation during runtime.

This makes them flexible.

Dynamic Priority Queue Using Vector in C++

#include <iostream>
#include <vector>
using namespace std;

class DynamicPriorityQueue {
    private:
    vector<int> heap;

    public:
    void insert(int value) {
        heap.push_back(value);
        int i = heap.size() - 1;

        while(i > 0 && heap[(i - 1)/2] < heap[i]) {
            swap(heap[i], heap[(i - 1)/2]);
            i = (i - 1)/2;
        }
    }

    void deleteMax() {
        if(heap.empty()) return;

        heap[0] = heap.back();
        heap.pop_back();

        int i = 0;

        while(true) {
            int left = 2*i + 1;
            int right = 2*i + 2;
            int largest = i;

            if(left < heap.size() && heap[left] > heap[largest])
                largest = left;

            if(right < heap.size() && heap[right] > heap[largest])
                largest = right;

            if(largest != i) {
                swap(heap[i], heap[largest]);
                i = largest;
            } else {
                break;
            }
        }
    }

    void display() {
        for(int val : heap)
            cout << val << " ";
        cout << endl;
    }
};

int main() {
    DynamicPriorityQueue pq;

    pq.insert(25);
    pq.insert(80);
    pq.insert(60);
    pq.insert(90);

    pq.display();

    pq.deleteMax();
    pq.display();

    return 0;
}

Array-Based vs Dynamic Priority Queue

Objective 3: Apply Priority Queue in Real-Life Example

Priority Queues are everywhere.

1. Hospital Emergency System

Patients are assigned priority:

• Critical → Highest
• Serious → Medium
• Normal → Low

Heap Tree ensures urgent patients are treated first.

2. CPU Task Scheduling

Operating systems assign priority to tasks.

Example:

• Antivirus scan → Medium
• Video rendering → High
• Background update → Low

The CPU processes higher-priority tasks first.

3. Airline Ticket Booking

Priority can be given to:

• Business Class
• Premium Economy
• Economy

Heap-based systems manage customer servicing.

4. Network Packet Routing

Routers prioritize packets:

• Video calls → High
• File downloads → Low

This improves performance.

Common Interview Questions

What is the difference between Queue and Priority Queue?

Queue: FIFO
Priority Queue: Based on priority

Why is Heap preferred?

Because it supports:

• Efficient insertion
• Efficient deletion
• O(log n) complexity

What is Heapify?

Heapify is the process of rearranging elements to maintain heap property.

Advantages of Heap Tree Priority Queue

✔ High efficiency
✔ Fast retrieval
✔ Real-world usability
✔ Easy implementation

Challenges

✖ Slightly complex implementation
✖ Tree balancing required
✖ Dynamic memory overhead

Best Practices for Students

When implementing:

• Always maintain heap property
• Test insertion and deletion
• Handle empty queue cases
• Use vectors for flexibility

Learning Outcomes

After completing this lab, students will be able to:

• Design array-based priority queues
• Design dynamic priority queues
• Implement heap insertion and deletion
• Apply priority queues to real systems
• Analyze heap performance

Weighted Task:

Student Assignment Submission Portal

A university has developed an Assignment Submission Portal to manage and process student assignments efficiently. Since many students submit their assignments at different times, the system must prioritize assignments based on their submission deadline urgency.

The portal uses a Priority Queue implemented using a Heap Tree, where assignments with fewer hours remaining before the deadline are processed first.

The following assignment submissions are currently in the system:

The system processes assignments according to priority order, ensuring urgent submissions are handled first.

Questions

a) Identify which student’s assignment will be processed first and explain why.

b) Draw the Max Heap Tree representation for the given data based on priority levels.

c) Write the array representation of the heap.

d) If another student, Hassan, submits an assignment with 1 hour left before deadline, show how the heap will be updated after insertion.

e) Explain why a Priority Queue using Heap Tree is more suitable for this system compared to a normal queue.

Conclusion

Heap Tree as a Priority Queue is a fundamental concept in data structures and algorithms.

It is used in:

• Operating systems
• Hospital management
• Task scheduling
• Networking
• Artificial intelligence

By mastering both array-based and dynamic implementations, students develop strong problem-solving skills and gain practical knowledge applicable in software development and system design.

Understanding this lab thoroughly builds the foundation for advanced topics like:

• Dijkstra’s Algorithm
• A* Search
• Process Scheduling
• Graph Algorithms