Chapter 32: Heaps

Introduction to Priority Queues and Heaps

Introduction to Priority Queues (PQ)

A Priority Queue (PQ) is a specialized type of queue where each element is assigned a priority. Elements with higher priority are processed before those with lower priority. Unlike a standard queue, which follows the First-In-First-Out (FIFO) principle, a priority queue ensures that elements are dequeued in the order of their priority rather than their arrival time.

For instance, if you think of a hospital emergency room, patients with more critical conditions are treated before those with less severe conditions, regardless of when they arrived. Similarly, in a priority queue, elements are removed based on their priority level.

Priority Queues in Java Collection Framework (JCF)

In Java, the PriorityQueue class is a part of the Java Collection Framework (JCF) and provides a concrete implementation of a priority queue. Internally, it uses a data structure called a binary heap to manage the elements. The elements in a PriorityQueue can be ordered either according to their natural ordering (for example, numbers in ascending order) or according to a custom order specified by a comparator.

Key Characteristics of PriorityQueue:

• Natural Ordering: Elements are ordered based on their inherent properties. For example, in a queue of numbers, smaller numbers might have higher priority if we're using a min-heap approach.

• Custom Ordering: You can provide a custom comparator to determine how elements are prioritized. This allows for more complex sorting criteria beyond natural ordering.

• No Duplicate Elements: If an element is added to the queue multiple times, it will be stored as distinct entries if the priority remains the same.

    import java.util.PriorityQueue;
  
    public class PrioQue {
        static class Student {
        int rollno;
  
        }
        public static void main(String[] args) {
            PriorityQueue<Integer>pq=new PriorityQueue<>();
            pq.add(3);
            pq.add(4);
            pq.add(1);
            pq.add(7);
            while (!pq.isEmpty()) {
                System.out.println(pq.peek());
                pq.remove();
            }
        }
    }
  

Priority Queues for Objects

When dealing with custom objects in a priority queue, it's important to ensure that these objects can be compared to determine their order. This can be achieved in two ways:

1. Natural Ordering: If your object class implements an interface that allows it to be compared (like Comparable), you can use this natural ordering to manage the priority.

2. Custom Ordering: You can use a comparator to specify the order explicitly when creating the priority queue. This is useful when you want to order objects based on specific attributes or criteria.

    public class PriQJCF {
        static class Student implements Comparable<Student> {
            int rank;
            String name;
            Student(int rank,String name){
                this.rank=rank;
                this.name=name;
            }
            @Override
            public int compareTo(Student s2){
                return this.rank-s2.rank;
            }
   
        }
        public static void main(String[] args) {
   
        }
    }
   

Introduction to Heaps

A heap is a tree-based data structure that satisfies the heap property. The heap property dictates that in a max-heap, each parent node has a value greater than or equal to its children, while in a min-heap, each parent node has a value less than or equal to its children. This property makes heaps ideal for implementing priority queues.

Heaps are commonly represented using a binary tree structure where each node has at most two children. The root of the heap is either the maximum or minimum element, depending on whether it's a max-heap or min-heap.

Heap Implementation Using Complete Binary Tree (CBT)

Heaps are often implemented using a complete binary tree (CBT), which is a binary tree where all levels are fully filled except possibly for the last level, which is filled from left to right. This structure allows heaps to be efficiently represented in an array.

In an array representation:

• The root of the heap is at index 0.

• The left child of any element at index i is located at index 2*i + 1.

• The right child of any element at index i is located at index 2*i + 2.

• The parent of any element at index i is located at index (i - 1) / 2.

Insertion in a Heap

To insert an element into a heap:

1. Add the Element: Place the new element at the end of the heap (i.e., the last position in the array).

2. Restore Heap Property: Compare the added element with its parent and swap them if necessary to maintain the heap property. This process is called "heapify up" or "bubble up".

3. Repeat: Continue this process until the heap property is restored, or the element reaches the root.

Peek from a Heap

To peek at the heap, simply look at the root of the heap. In a max-heap, this will be the largest element, and in a min-heap, it will be the smallest element. Peeking does not remove the element from the heap.

import java.util.ArrayList;

public class Insert {
    static class Heap {
        ArrayList<Integer> p=new ArrayList<>();
    public void inser(int data){
        //Add at Last 
        p.add(data);
        int child=p.size()-1;
        int parent=(child-1)/2;

        //Swap
        while (p.get(child)<p.get(parent)) {
            int temp=p.get(parent);
            p.set(child, p.get(parent));
            p.set(parent, temp);
        }
    }
        public int peek(){
            return p.get(0);
        }
    }

    public static void main(String[] args) {
       Heap heap=new Heap();
       heap.inser(2);
    }
}

Remove from a Heap

To remove the root element from a heap:

1. Replace the Root: Replace the root with the last element in the heap (i.e., the last position in the array).

2. Remove the Last Element: Remove the last element from the heap.

3. Restore Heap Property: Reorganize the heap to maintain its properties by "heapifying down" or "sifting down" the new root. This involves comparing the root with its children and swapping it with the appropriate child until the heap property is restored.

    import java.util.ArrayList;
   
    public class Remove {
           static class Heap {
            ArrayList<Integer> p=new ArrayList<>();
        public void insert(int data){
            //Add at Last 
            p.add(data);
            int child=p.size()-1;
            int parent=(child-1)/2;
   
            //Swap
            while (p.get(child)<p.get(parent)) {
                int temp=p.get(child);
                p.set(child, p.get(parent));
                p.set(parent, temp);
                child=parent;
                parent=(child-1)/2;
            }
        }
            public int peek(){
                return p.get(0);
            }
            private void heapify(int i){
                int left=2*i+1;
                int right=2*i+2;
                int minidx=i;
                if(left<p.size() && p.get(minidx)>p.get(left)){
                    minidx=left;
                }
                if(right<p.size() && p.get(minidx)>p.get(right)){
                    minidx=right;
                }
                if (minidx!=i) {
                    // Swap
                    int temp=p.get(i);
                    p.set(i, p.get(minidx));
                    p.set(minidx, temp);
                    heapify(minidx);
                }
            }
            public int remove(){
                int data=p.get(0);
                //Step 1: Swap First and Last
                int temp=p.get(0);
                p.set(0,p.get( p.size()-1));
                p.set(p.size()-1, temp);
   
                //Step 2:remove
                p.remove(p.size()-1);
   
                //Step3: Heapify
                heapify(0);
                return data;
            }
            public boolean isEmpty(){
                return p.size()==0;
            }
        }
        public static void main(String[] args) {
            Heap h=new Heap();
            h.insert(3);
            h.insert(4);
            h.insert(1);
            h.insert(5);
            while(!h.isEmpty()){
                System.out.println(h.peek());
                h.remove();
            }
         }
    }
   

Heap Sort

Heap sort is a sorting algorithm that uses a heap data structure to sort elements. The process involves:

1. Build a Max-Heap: Convert the array of elements into a max-heap.

2. Extract Maximum: Remove the root (maximum element) of the heap and place it at the end of the array.

3. Re-heapify: Restore the heap property by heapifying the root.

4. Repeat: Continue extracting the maximum element and re-heapifying until the heap is empty.

    import java.util.Scanner;
   
    public class HeapSort {
        public static void heapify(int arr[],int i,int size){
            int left=2*i+1;
            int right=2*i+2;
            int maxidx=i;
            if (left<size && arr[left]>arr[maxidx]) {
                maxidx=left;
            }
            if (right<size && arr[right]>arr[maxidx]) {
                maxidx=right;
            }
            if (maxidx!=i) {
                //Swap
                int temp=arr[i];
                arr[i]=arr[maxidx];
                arr[maxidx]=temp;
                heapify(arr, maxidx, size);
            }
        }
        public static void heapSort(int arr[]){
            //Step 1: Bulid MaxHeap
            int n=arr.length;
            for (int i = n/2; i >=0; i--) {
                heapify(arr, i, n);
            }
            //Step 2: Push larget at end
            for (int i =n-1; i >0; i--) {
                //Swap
                int temp=arr[0];
                arr[0]=arr[i];
                arr[i]=temp;
                heapify(arr, 0, i);
            }
        }
        public static void main(String args[]){
            int arr[]={1,2,4,5,3};
            heapSort(arr);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
   
    }
   

Nearby Cars Problem

Problem Description

Imagine you're standing at the origin of a 2D plane, which is the point (0,0). You're given the locations of N cars on this plane, and you need to find the k nearest cars to the origin. Each car's location is represented by coordinates (x, y) on this plane.

For instance, let's say you have the following cars:

• Car C0 is located at (3,3)

• Car C1 is located at (5,-1)

• Car C2 is located at (-2,4)

In this case, you want to find the 2 nearest cars to the origin (0,0).

Steps to Solve the Problem

1. Calculate Distances: The distance of each car from the origin can be computed using the Euclidean distance formula. For a car located at (x, y), the distance from the origin (0,0) is given by:

   {Distance} = sqrt{x^2 + y^2}

   You don’t need to compute the square root for comparison purposes; the squared distance (x^2 + y^2) is sufficient.

2. Compute Distances for Each Car:

   • For Car C0 at (3,3): [ {Distance}^2 = 3^2 + 3^2 = 9 + 9 = 18 ]

   • For Car C1 at (5,-1): [ {Distance}^2 = 5^2 + (-1)^2 = 25 + 1 = 26 ]

   • For Car C2 at (-2,4): [ {Distance}^2 = (-2)^2 + 4^2 = 4 + 16 = 20 ]

3. Compare Distances: Next, compare these distances to determine which cars are the closest to the origin. Based on the squared distances calculated:

   • Car C0 has a distance squared of 18.

   • Car C2 has a distance squared of 20.

   • Car C1 has a distance squared of 26.

Clearly, Car C0 is the closest, followed by Car C2, and then Car C1.

4. Select the Nearest Cars: Since we need the k nearest cars, and k=2 in this example, we select the two cars with the smallest distances:

   • Car C0 (Distance squared: 18)

   • Car C2 (Distance squared: 20)

5. Print the Results: The nearest cars to the origin, based on the calculated distances, are Car C0 and Car C2.

Summary

To solve the Nearby Cars problem:

• Calculate the squared distance of each car from the origin.

• Compare these distances to identify the nearest cars.

• Select the k cars with the smallest distances.

import java.util.PriorityQueue;

public class NearbyCars {
    static class Point implements Comparable<Point> {
        int x;
        int y;
        int distSq;
        int idx;
        public Point(int x,int y,int distSq,int idx){
            this.x=x;
            this.y=y;
            this.idx=idx;
            this.distSq=distSq;
        }
        @Override
        public int compareTo(Point p2){
            return this.distSq-p2.distSq;
        }

    }
    public static void main(String[] args) {
        int pts[][]={{3,3},{5,-1},{-2,4}};
        int k=2;
        PriorityQueue<Point> pq=new PriorityQueue<>();
        for (int i = 0; i < pts.length; i++) {
            int distSq=pts[i][0]*pts[i][0]+pts[i][1]*pts[i][1];
            pq.add(new Point(pts[i][0], pts[i][1], distSq,i));
        }

        // Nearest K cars
        for (int i = 0; i < k; i++) {
            System.out.println("C"+pq.remove().idx);
        }
    }
}

Detailed Explanation of the Nearby Cars Problem with Code

The code provided demonstrates how to solve the Nearby Cars problem using a priority queue to efficiently identify the nearest k cars from a set of given car positions. Let's break down the code and explain each part in detail:

Code Breakdown

1. Imports and Class Definition:

    import java.util.PriorityQueue;
   

   This import statement brings in the PriorityQueue class from the Java Collections Framework, which is used to manage a collection of elements ordered by their priority.

    public class NearbyCars {
   

   The NearbyCars class contains the logic to find the nearest cars.

2. Inner Class Definition:

    static class Point implements Comparable<Point> {
        int x;
        int y;
        int distSq;
        int idx;
   
        public Point(int x, int y, int distSq, int idx) {
            this.x = x;
            this.y = y;
            this.distSq = distSq;
            this.idx = idx;
        }
   
        @Override
        public int compareTo(Point p2) {
            return this.distSq - p2.distSq;
        }
    }
   

   The Point class represents a car's position and its distance from the origin. It implements the Comparable interface to allow comparison based on the distance squared (distSq), which is used for sorting in the priority queue.

   • Attributes:

     • x and y represent the coordinates of the car.

     • distSq is the squared distance from the origin, calculated to avoid the overhead of computing square roots.

     • idx is the index of the car, used to identify the car in the output.

   • Constructor: Initializes the car's position, distance squared, and index.

   • compareTo Method: This method is used to define the order in which points are stored in the priority queue. It orders the points by their distance squared (distSq), ensuring that the closest points come first.

3. Main Method:

    public static void main(String[] args) {
        int pts[][] = {{3, 3}, {5, -1}, {-2, 4}};
        int k = 2;
        PriorityQueue<Point> pq = new PriorityQueue<>();
   

   • pts[][] is a 2D array where each inner array represents the coordinates of a car.

   • k is the number of nearest cars you want to find.

   • pq is a priority queue that will store Point objects and automatically order them based on their distance squared.

        for (int i = 0; i < pts.length; i++) {
            int distSq = pts[i][0] * pts[i][0] + pts[i][1] * pts[i][1];
            pq.add(new Point(pts[i][0], pts[i][1], distSq, i));
        }

This loop iterates through each car's position, calculates the squared distance from the origin (to avoid computing the square root), and adds a new Point object to the priority queue.

        for (int i = 0; i < k; i++) {
            System.out.println("C" + pq.remove().idx);
        }
    }

This loop extracts the k nearest cars from the priority queue. Since the priority queue is ordered by distance, removing elements from it gives the nearest cars first. The idx attribute is used to identify and print each car.

How It Works

1. Distance Calculation:

   • The squared distance is calculated for each car using the formula ( {distSq} = x^2 + y^2 ). This avoids the computational expense of taking the square root, which is unnecessary for comparison purposes.

2. Priority Queue Operations:

   • The priority queue automatically maintains the order of elements based on the distance squared. The closest cars (with the smallest distance squared) are always at the front of the queue.

3. Extracting Nearest Cars:

   • By removing the top k elements from the priority queue, you get the indices of the k nearest cars. These indices correspond to the closest cars based on their distance from the origin.

Summary

This code efficiently finds and prints the nearest k cars from a given list of positions. By using a priority queue, it maintains the nearest cars in a sorted order based on their distance from the origin. The approach ensures that the solution is both effective and efficient, leveraging the properties of the priority queue to handle the sorting and extraction of nearest elements.

Connect N Ropes with Minimum Cost

In this problem, you need to connect N ropes of varying lengths into a single rope with the minimum cost. The cost to connect two ropes is the sum of their lengths. To minimize the total cost, you can use a priority queue to always connect the two shortest ropes first.

Weakest Soldier Problem

The weakest soldier problem involves finding the soldier with the least strength in a line of soldiers. By using a priority queue, you can efficiently determine which soldier has the lowest strength by maintaining an ordered list based on strength values.

Sliding Window Problem

The sliding window problem involves finding optimal solutions within a moving window of elements. This approach is useful for problems like finding the maximum or minimum value in a subarray. A priority queue or deque can be used to manage and update the window's content efficiently as it slides over the sequence.

---

Conclusion

Understanding priority queues and heaps is fundamental to solving a wide range of computational problems efficiently. Priority queues are versatile data structures that manage elements based on their priority rather than their order of insertion, making them invaluable for tasks such as scheduling, resource management, and real-time systems. The underlying heap structure enables priority queues to offer optimal performance in insertion and removal operations.

Heaps, with their complete binary tree representation, provide a powerful mechanism for implementing priority queues. The heap property ensures that the highest or lowest priority element is always accessible, which is essential for efficiently managing dynamic sets of elements. By maintaining this property, heaps facilitate operations like insertion, deletion, and sorting with predictable performance.

Practical problems such as connecting ropes with minimal cost, finding nearby cars, and sorting elements can all benefit from the principles of heaps and priority queues. Their applications extend to real-world scenarios, including task scheduling, resource allocation, and data stream management.

In summary, mastering priority queues and heaps equips you with the tools to tackle complex problems efficiently and effectively, making these concepts a crucial part of any programmer’s toolkit. Whether you’re dealing with dynamic data sets or optimizing performance for specific tasks, understanding and applying these data structures will significantly enhance your problem-solving capabilities.