A Binary Heap is a complete binary tree that satisfies the heap property. It can be either a max heap or a min heap. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, the value of I is less than or equal to the values of its children.

Priority Queue Basics

A Priority Queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.


import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>();
      pq.add(10);
      pq.add(20);
      pq.add(15);
      System.out.println(pq);
  }
}

Min Heap Implementation

In a Min Heap, the root node is the smallest element. Every parent node has a value smaller than or equal to any of its children.

Console Output:

[10, 20, 15]

Max Heap Structure

Max Heap Characteristics

In a Max Heap, the root node is the largest element. All parent nodes have a value greater than or equal to any of their children.


import java.util.Collections;
import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());
      pq.add(10);
      pq.add(20);
      pq.add(15);
      System.out.println(pq);
  }
}

Utilizing Max Heap

Max Heaps are often used in implementing priority queues where the highest priority element is always dequeued first.

Console Output:

[20, 10, 15]

Heap Sort Algorithm

Understanding Heap Sort

Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.


import java.util.Arrays;
import java.util.PriorityQueue;
class Example {
  public static void heapSort(int[] arr) {
      PriorityQueue pq = new PriorityQueue<>();
      for (int num : arr) {
          pq.add(num);
      }
      int index = 0;
      while (!pq.isEmpty()) {
          arr[index++] = pq.poll();
      }
  }
  public static void main(String args[]) {
      int[] arr = {3, 5, 1, 10, 2};
      heapSort(arr);
      System.out.println(Arrays.toString(arr));
  }
}

Efficiency of Heap Sort

Heap Sort has a time complexity of O(n log n) and is not a stable sort. It is often used in scenarios where a stable sort is not required.

Console Output:

[1, 2, 3, 5, 10]

Building a Binary Heap

Binary Heap Construction

Building a Binary Heap can be done in O(n) time complexity using the heapify method. This is more efficient than inserting elements one by one into an empty heap.


import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      int[] arr = {3, 5, 1, 10, 2};
      PriorityQueue pq = new PriorityQueue<>();
      for (int num : arr) {
          pq.add(num);
      }
      System.out.println(pq);
  }
}

Heapify Process

The heapify process involves arranging the elements in such a way that the heap property is maintained. This is done by repeatedly applying the sift-down operation.

Console Output:

[1, 2, 3, 10, 5]

Applications of Priority Queue

Real-world Usage

Priority Queues are used in various real-world applications such as CPU scheduling, Disk Scheduling, Dijkstra's algorithm, and Prim's algorithm.


import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>();
      pq.add("Low");
      pq.add("Medium");
      pq.add("High");
      while(!pq.isEmpty()) {
          System.out.println(pq.poll());
      }
  }
}

Priority Levels

Elements in a priority queue are dequeued based on their priority levels. Higher priority elements are processed first.

Console Output:

High Medium Low

Custom Comparator in Priority Queue

Using Comparators

Priority Queues can be customized using Comparators to order elements based on specific criteria rather than natural ordering.


import java.util.Comparator;
import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());
      pq.add(10);
      pq.add(20);
      pq.add(15);
      System.out.println(pq);
  }
}

Custom Ordering

Using custom comparators allows for flexibility in how elements are prioritized, enabling solutions tailored to specific needs.

Console Output:

[20, 10, 15]

Dynamic Priority Queue Operations

Modifying Priorities

Priority Queues allow dynamic modification of priorities. Elements can be removed and reinserted with new priorities as needed.


import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>();
      pq.add(20);
      pq.add(15);
      pq.add(30);
      pq.poll(); // Removing the highest priority element
      pq.add(25);
      System.out.println(pq);
  }
}

Handling Dynamic Data

Dynamic operations are crucial in real-time systems where data priorities frequently change, such as in network routing and load balancing.

Console Output:

[15, 25, 30]

Merging Two Heaps

Heap Merging Techniques

Merging two heaps involves combining elements from both heaps into a new heap that maintains the heap property. This can be achieved efficiently using priority queues.


import java.util.PriorityQueue;
class Example {
  public static void main(String args[]) {
      PriorityQueue pq1 = new PriorityQueue<>();
      pq1.add(10);
      pq1.add(20);
      PriorityQueue pq2 = new PriorityQueue<>();
      pq2.add(15);
      pq2.add(25);
      pq1.addAll(pq2);
      System.out.println(pq1);
  }
}

Efficient Merging

Heap merging is particularly useful in applications like external sorting and multi-way merge algorithms where large datasets are involved.

Console Output:

[10, 15, 20, 25]

Priority Queue with Custom Objects

Handling Custom Data Types

Priority Queues can handle objects by defining a custom Comparator that dictates the priority based on object attributes.


import java.util.PriorityQueue;
import java.util.Comparator;
class Task {
  String name;
  int priority;
  Task(String name, int priority) {
      this.name = name;
      this.priority = priority;
  }
}
class TaskComparator implements Comparator {
  public int compare(Task t1, Task t2) {
      return t1.priority - t2.priority;
  }
}
class Example {
  public static void main(String args[]) {
      PriorityQueue pq = new PriorityQueue<>(new TaskComparator());
      pq.add(new Task("Task1", 2));
      pq.add(new Task("Task2", 1));
      while(!pq.isEmpty()) {
          System.out.println(pq.poll().name);
      }
  }
}

Custom Object Prioritization

This approach is widely used in scheduling tasks, where each task is an object with attributes like priority, start time, and duration.

Console Output:

Task2 Task1