Heap selection is a method used in computer science for choosing elements from a heap data structure. Heaps are binary trees that satisfy the heap property, where the parent node is always greater than or equal to its child nodes in a max heap, or less than or equal to its child nodes in a min heap.


import java.util.PriorityQueue;

class HeapExample {
  public static void main(String[] args) {
    PriorityQueue minHeap = new PriorityQueue<>();
    minHeap.add(10);
    minHeap.add(30);
    minHeap.add(20);
    System.out.println("Min Heap Root: " + minHeap.peek());
  }
}

Min Heap Implementation

In this example, we demonstrate the creation of a min heap using Java's PriorityQueue. The smallest element is always at the root, which can be accessed using the peek method.

Console Output:

Min Heap Root: 10

Max Heap Implementation

Max Heap Using Comparator

A max heap can be implemented by providing a custom comparator to the PriorityQueue. This ensures the largest element is always at the root.


import java.util.Collections;
import java.util.PriorityQueue;

class MaxHeapExample {
  public static void main(String[] args) {
    PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    maxHeap.add(10);
    maxHeap.add(30);
    maxHeap.add(20);
    System.out.println("Max Heap Root: " + maxHeap.peek());
  }
}

Explanation

The max heap is achieved by reversing the natural order of elements. This way, the PriorityQueue behaves like a max heap, with the largest element at the top.

Console Output:

Max Heap Root: 30

Heap Sort Algorithm

Heap Sort Using Max Heap

Heap sort is a comparison-based sorting technique based on a binary heap data structure. It involves building a max heap from the input data and then repeatedly extracting the maximum element from the heap.


import java.util.Arrays;

class HeapSort {
  public void sort(int arr[]) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      heapify(arr, i, 0);
    }
  }

  void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
      largest = l;

    if (r < n && arr[r] > arr[largest])
      largest = r;

    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;
      heapify(arr, n, largest);
    }
  }

  public static void main(String args[]) {
    int arr[] = {12, 11, 13, 5, 6, 7};
    HeapSort ob = new HeapSort();
    ob.sort(arr);
    System.out.println("Sorted array is: " + Arrays.toString(arr));
  }
}

Explanation

This code demonstrates the heap sort algorithm. It first builds a max heap from the input array and then sorts the array by repeatedly removing the largest element from the heap.

Console Output:

Sorted array is: [5, 6, 7, 11, 12, 13]

Heap Selection in Priority Queues

Using Heaps for Task Scheduling

Priority queues implemented with heaps are often used for scheduling tasks. The highest priority task is always processed first.


import java.util.PriorityQueue;

class Task implements Comparable {
  int priority;
  String name;

  Task(int priority, String name) {
    this.priority = priority;
    this.name = name;
  }

  @Override
  public int compareTo(Task other) {
    return Integer.compare(other.priority, this.priority);
  }
}

class PriorityQueueExample {
  public static void main(String[] args) {
    PriorityQueue taskQueue = new PriorityQueue<>();
    taskQueue.add(new Task(1, "Low priority task"));
    taskQueue.add(new Task(3, "High priority task"));
    taskQueue.add(new Task(2, "Medium priority task"));

    while (!taskQueue.isEmpty()) {
      System.out.println("Processing: " + taskQueue.poll().name);
    }
  }
}

Explanation

This example shows how tasks with different priorities can be managed using a priority queue. Tasks are processed based on their priority, with the highest priority task being processed first.

Console Output:

Processing: High priority task

Processing: Medium priority task

Processing: Low priority task

Heap Implementation for Median Finding

Finding Median from Data Stream

Heaps can be used to efficiently find the median of a data stream. This is done by maintaining two heaps: a max heap for the lower half of numbers and a min heap for the upper half.


import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
  private PriorityQueue maxHeap;
  private PriorityQueue minHeap;

  public MedianFinder() {
    maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    minHeap = new PriorityQueue<>();
  }

  public void addNum(int num) {
    maxHeap.offer(num);
    minHeap.offer(maxHeap.poll());
    if (maxHeap.size() < minHeap.size()) {
      maxHeap.offer(minHeap.poll());
    }
  }

  public double findMedian() {
    if (maxHeap.size() == minHeap.size()) {
      return (maxHeap.peek() + minHeap.peek()) / 2.0;
    } else {
      return maxHeap.peek();
    }
  }

  public static void main(String[] args) {
    MedianFinder mf = new MedianFinder();
    mf.addNum(1);
    mf.addNum(2);
    System.out.println("Median: " + mf.findMedian());
    mf.addNum(3);
    System.out.println("Median: " + mf.findMedian());
  }
}

Explanation

This implementation uses two heaps to keep track of the median. The max heap stores the lower half of the numbers, while the min heap stores the higher half. The median can be quickly found by looking at the tops of these heaps.

Console Output:

Median: 1.5

Median: 2.0