Sharath Enugala

Data Structures - Understanding Heaps and Priority Queues through a Java Implementation

 

Jump to Source Code BinaryHeap PriorityQueue

 

In computer science, binary heaps and priority queues play a pivotal role, especially in areas like scheduling algorithms and graph processing. This blog post offers a deep dive into binary heaps and their usage in implementing priority queues, all through a comprehensive custom Java implementation.

 

What is a Binary Heap?

A binary heap is a complete binary tree that adheres to a specific heap property. It's classified into two types: min-heap, where the root has the minimum key, and max-heap, where the root has the maximum key. This characteristic holds true recursively for all its sub-trees.

 

Key Features of Binary Heap:

  • Complete Binary Tree: A complete binary tree is a type of binary tree where all levels, except possibly the last, are fully filled, and all nodes are as far left as possible. This guarantees a balanced structure for optimal height.
  • Heap Property: Ensures the correct order of elements according to min or max heap rules.

 

Java Implementation of Binary Heap

We focus on critical methods of the BinaryHeap class, which uses an array internally to represent the heap.

1. insert

Inserts a new element into the heap, adding it at the end of the array and then performing a heapify-up operation to maintain the heap property.

public void insert(int data) {
    if (size >= capacity) return; 
    heapArray[size] = data; 
    heapifyUp(size);
    size++;
}

 

2.extractMinOrMax

This method extracts the minimum or maximum element from the heap, typically the root and removes from heap.

public int extractMinOrMax() {
    if (isEmpty()) 
    throw new 
    NoSuchElementException(
        "Heap is empty");
    // Min or Max is allways stored 
    //at the index zero(top)
    int value = heapArray[0]; 
    deleteKey(0); //delete root
    return value;
}

 

3.deleteKey

Deletes an element at a specific index in the heap, swapping it with the last element and then performing a heapify-down operation.

public void deleteKey(int i) {
    swap(i, size - 1);
    size--;
    heapifyDown(i);
}

   

What is a Priority Queue?

A priority queue is a data structure where each element is associated with a priority. Elements with higher priority are served before those with lower priority.

 

Implementing Priority Queue with BinaryHeap

Our PriorityQueue class utilizes above BinaryHeap for its operations.

Key Methods in PriorityQueue:

1.enqueue

Adds an element to the queue using the BinaryHeap's insert method.

public void enqueue(int element) {
    heap.insert(element);
}

 

2.dequeue

Removes and returns the element with the highest (or lowest) priority, utilizing the BinaryHeap's extractMinOrMax method.

public int dequeue() {
    if (!isEmpty()) {
        return heap.extractMinOrMax()
    }
    throw new 
    NoSuchElementException(
        "Priority queue is empty");
}

 

3.peek

Returns the highest (or lowest) priority element without removing it from the queue.

public int peek() {
    if (!isEmpty()) {
        return heap.getMinOrMax();
    }
    throw new NoSuchElementException(
        "Priority queue is empty");
}

 

Conclusion

Binary heaps and priority queues are essential data structures in software engineering, offering efficient ways to manage prioritized data with frequent additioins and deletions. They are crucial in operating systems for process scheduling, in networking for packet management, and in real-time systems for task prioritization. Additionally, heaps are used in data stream analysis and pathfinding algorithms in graph processing.

 

Complete Source Code

BinaryHeap   PriorityQueue

← Back to home