Binary Heap DSA

Binary Heap DSA | A binary heap is an essential data structure used in algorithms such as HeapSort and the implementation of Priority Queues. There are two primary types:

• Min Heap: In this type, the item with the lowest value is given the highest priority. Consequently, the smallest element is always positioned at the top of the heap. When an element is removed, it is always the one with the lowest value.
• Max Heap: In this type, the item with the highest value is given the highest priority. Thus, the largest element is always positioned at the top of the heap. When an element is removed, it is always the one with the highest value.

Each type ensures that the highest priority item is efficiently accessible at all times.

Table of Contents

• Binary Heap Implementation
• Heap Insert Operation
• Binary Heap Heapify
  • Convert Min Heap to Max Heap
• Binary Heap – Extract Min
• Decrease Key
• Delete Key
• Build Heap
• Heap Sort
• PriorityQueue Class in Java
• Sort a K-Sorted Array
• Buy Maximum Items with the Given Sum
• K Largest Elements
• K Closest Elements
• Merge K-Sorted Arrays
• The median of a Stream

---

Binary Heap is a complete Binary Tree (sorted as an array). What is a complete binary tree? A complete binary tree is a type of binary tree where every level, except possibly the last, is completely filled, and all nodes are as far left as possible. In simpler terms, it’s a binary tree in which all levels are fully populated with nodes, except for the last level, where the nodes are filled from left to right.

Indexes are calculated as follows:-
left(i) = 2*i + 1
right(i) = 2*i + 2
parent(i) = floor( (i-1)/2 )

Examples:-
left(1) = 3
right(1) = 4
parent(5) = 2

Min Heap

• It is a complete Binary Tree.
• Every node has a value smaller than its descendants (subtree).
• Each parent node is less than or equal to its children.
• The root node contains the minimum value.

       1
      / \
     3   2
    / \
   5   4

Array Representation: [1, 3, 2, 5, 4]

        10
       /  \
      15   20
     / \   / \
    30  40 50 60

Array Representation: [10, 15, 20, 30, 40, 50, 60]

       7
      / \
     12  15
    / \  / \
   20 18 30 25

Array Representation: [7, 12, 15, 20, 18, 30, 25]

Binary Heap Implementation

public class MinHeap {
    int arr[];
    int size;
    int capacity;

    public MinHeap(int c) {
        arr = new int[c];
        size = 0;
        capacity = c;
    }

    private int left(int i) {
        return 2 * i + 1;
    }

    private int right(int i) {
        return 2 * i + 2;
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    // helper
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Heap Insert Operation

The insertion operation ensures that the min-heap property is maintained after adding a new element. Steps for Min Heap Insertion:-

1. Add the Element at the End: Insert the new element at the end of the heap (i.e., the next available position in the array representation).
2. Heapify-Up:

• Compare the added element with its parent (at index floor((i-1)/2).
• If the added element is smaller than its parent, swap them.
• Repeat this process until the new element is in a position where it is no longer smaller than its parent (i.e., the min-heap property is restored).

Example: Let’s insert the element 2 into the following min heap:

       1
      / \
     3   5
    / \
   7   8

Array Representation: [1, 3, 5, 7, 8]

Insert 2:

1. Add 2 at the end:

          1
         / \
        3   5
       / \  /
      7   8 2

Array Representation: [1, 3, 5, 7, 8, 2]

2. Heapify-Up:

• Compare 2 (at index=5) with its parent at index floor((5-1)/2) = arr[2] = 5. Since 2 < 5, swap them.
• After the swap:

          1
         / \
        3   2
       / \  /
      7   8 5

Array Representation: [1, 3, 2, 7, 8, 5]

• Compare 2 (now at index 2) with its new parent 1 (index 0). Since 2 > 1, no swap is needed, and the heapify-up process stops.

public void insert(int k) {
    // Check if the heap is full
    if (size == capacity) {
        // Typically, libraries use dynamic arrays to handle this
        return;
    }

    // Increase the size of the heap
    size++;

    // Insert the new element at the end of the array
    arr[size - 1] = k;

    // Heapify-up to maintain the min heap property
    for (int i = size - 1; i != 0 && arr[parent(i)] > arr[i]; i = parent(i)) {
        // Swap the current element with its parent
        swap(arr, i, parent(i));
    }
}

Test:-

public class MinHeapTest {
    public static void main(String[] args) {
        // Create a MinHeap with capacity of 10
        MinHeap heap = new MinHeap(10);

        // Test insert operation
        heap.insert(3);
        heap.insert(2);
        heap.insert(1);
        heap.insert(15);
        heap.insert(5);
        heap.insert(4);
        heap.insert(45);

        // Print the heap array after insertions
        printHeapArray(heap);
    }

    // Helper method to print heap array
    private static void printHeapArray(MinHeap heap) {
        for (int i = 0; i < heap.size; i++) {
            System.out.print(heap.arr[i] + " ");
        }
        System.out.println();
    }
}

Output:-
1 3 2 15 5 4 45

Binary Heap Heapify

Min Heapfiy: Given a Binary Heap with one possible violation, fix the Heap. Similar Problem.

       40
      /   \
     20    30
    /  \   / \
   35  25 80 32
  / \  /
100 70 60

Array Representation: [40, 20, 30, 35, 25, 80, 32, 100, 70, 60]. The violation is at the root level itself.
Steps to Fix the Min Heap:

1. Identify the Violation: Find the node that violates the min-heap property. Compare the parent with its child, the child value is supposed to be greater than parent. The violation is at the root node 40.
2. Swap the nodes:

       20
      /   \
     40    30
    /  \   / \
   35  25 80 32
  / \  /
100 70 60

Array Representation: [20, 40, 30, 35, 25, 80, 32, 100, 70, 60]

3. Recursively call heapify for child subtree.
   Now, 40 (index 1) is compared with its new children 35 (left) and 25 (right).
   Swap 40 with 25 because 25 < 35.

       20
      /   \
     25    30
    /  \   / \
   35  40 80 32
  / \  /
100 70 60

Code implementation:-

// Considering the ith node violates the Heap property
public void minHeapify(int i) {
    // Find whether left or right child violates the heap property
    int lt = left(i), rt = right(i);
    int smallest = i;

    // Check if left child is smaller than the current node
    if (lt < size && arr[lt] < arr[smallest]) {
        smallest = lt;
    }

    // Check if right child is smaller than the smallest found so far
    if (rt < size && arr[rt] < arr[smallest]) {
        smallest = rt;
    }

    // If the smallest is not the current node, swap and continue heapifying
    if (smallest != i) {
        // Swap the current node with the smallest child
        swap(arr, i, smallest);

        // Recursive call to heapify the affected subtree
        minHeapify(smallest);
    }
}

• Time complexity: O(log n). O(1) in the best case, O(h) in the worst case, h for min heap is log n so O(log n).
• Auxiliary space: O(h). However, it can be easily converted into an iterative solution where auxiliary space will be O(1).

Convert Min Heap to Max Heap

You are given an array arr of N integers representing a min Heap. The task is to convert it to max Heap. Problem.

A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.

Input:
N = 4
arr = [1, 2, 3, 4]

Output: [4, 2, 3, 1]

class Solution {
    static void convertMinToMaxHeap(int N, int arr[]) {
        // Start from the last non-leaf node and heapify each node
        for (int i = (N - 2) / 2; i >= 0; i--) {
            heapify(arr, N, i);
        }
    }

    // Function to heapify a subtree rooted at index i
    static void heapify(int arr[], int N, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // left = 2*i + 1
        int right = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (left < N && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than the current largest
        if (right < N && arr[right] > arr[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected subtree
            heapify(arr, N, largest);
        }
    }
}

Binary Heap – Extract Min

The root contains the minimum element so fetching/getting minimum element has time complexity O(1) as it does not require any array modification. In for extracting the minimum we have to remove the minimum element and maintain the properties of Binary Heap.

       20
      /   \
     25    30
    /  \   / \
   35  40 80 32
  / \  /
100 70 60

After extracting min (20):-

       25
      /   \
     35    30
    /  \   / \
   60  40 80 32
  / \  
100 70 

Steps for Extracting Min from a Min Heap:

1. Check if the Heap is Empty: If the heap is empty, return an appropriate message or value indicating that extraction cannot be performed.
2. Swap root and last element
3. Reduce the Size of the Heap: Decrease the size of the heap by one to remove the last element from consideration.
4. Heapify-Down from the Root: Call the minHeapify function starting from the root to restore the min-heap property. This function ensures that the heap remains a valid min heap by comparing the root with its children and performing necessary swaps.

public int extractMin() {
    // Check if the heap is empty
    if (size == 0) {
        return Integer.MAX_VALUE;
    }

    // If there's only one element in the heap
    if (size == 1) {
        size--;
        return arr[0];
    }

    // swap
    int min = arr[0];
    arr[0] = arr[size-1];

    // Decrease the size of the heap
    size--;

    // Restore the heap property by heapifying from the root
    minHeapify(0);

    return min;
}

Test:-

printHeapArray(heap);
System.out.println("Extracted min element: " + heap.extractMin());
System.out.println("Heap array after extractMin:");
printHeapArray(heap);

Output:-
1 3 2 15 5 4 45
Extracted min element: 1
Heap array after extractMin:
2 3 4 15 5 45

Both time complexity and auxiliary space is same as minHeapify() because all other operations are doing constant work.

Decrease Key

We have a binary heap, an index of an element, and its new value. Update the new value and preserve the Binary Heap property.

        10
      /    \
     20     40
    /  \    /
   80  100  70

i=3, x=5. So, replace 80 with 5, and maintain Binary Heap property.
Output:-

        5
      /    \
     10     40
    /  \    /
   20  100  70

Steps for Decrease Key in a Min Heap:

1. Identify the Index: Determine the index of the element whose key needs to be decreased.
2. Decrease the Key: Update the value of the key at the identified index to the new, lower value.
3. Heapify-Up:

• Compare the updated key with its parent.
• If the updated key is smaller than its parent, swap them.
• Continue this process until the heap property is restored (i.e., the updated key is not smaller than its parent).

Example: Initial Min Heap:

       10
      /  \
     20   15
    / \   / \
   35 25 30 40

Array Representation: [10, 20, 15, 35, 25, 30, 40]

Decrease the Key at Index 3 (from 35 to 5):

1. Identify the Index: The index of the key to be decreased is 3.
2. Decrease the Key: Update the value at the index 3 from 35 to 5. Array Representation: [10, 20, 15, 5, 25, 30, 40]
3. Heapify-Up:

• Compare 5 (index 3) with its parent 20 (index 1). Since 5 < 20, swap them.

           10
          /  \
         5    15
        / \   / \
       20  25 30 40

Array Representation: [10, 5, 15, 20, 25, 30, 40]

• Now, compare 5 (index 1) with its parent 10 (index 0). Since 5 < 10, swap them.

           5
          /  \
         10   15
        / \   / \
       20  25 30 40

Array Representation: [5, 10, 15, 20, 25, 30, 40]

• Now, 5 is at the root, and no further swaps are needed.

public void decreaseKey(int i, int x) {
    // Set the element at index i to the new value x
    arr[i] = x;

    // Heapify-up to restore the min heap property
    while (i != 0 && arr[parent(i)] > arr[i]) {
        // Swap the element with its parent if it's smaller
        swap(arr, i, parent(i));

        // Move to the parent index
        i = parent(i);
    }
}

Test:-

printHeapArray(heap);
heap.decreaseKey(3, 3);
System.out.println("Heap array after decreaseKey:");
printHeapArray(heap);

Output:-
1 3 2 15 5 4 45
Heap array after decreaseKey:
1 3 2 3 5 4 45

Delete Key

We have a binary heap, an index of an element. Delete the index value and preserve the Binary Min Heap property:-

• Parent node must always be less than or equal to its child nodes.
• The tree must remain a complete binary tree, where every level is fully filled except possibly the last, which is filled from left to right.

Steps to Delete an Element by Replacing with Integer.MIN_VALUE:

1. Replace with Integer.MIN_VALUE: Replace the element at the specified index with Integer.MIN_VALUE.
2. Heapify-Up to Move to Root: Perform the heapify-up operation to move Integer.MIN_VALUE to the root.
3. Extract Min: Perform the extractMin operation to remove the root (which is now Integer.MIN_VALUE).

public void delete(int i) {
    // Replace the element at index i with Integer.MIN_VALUE
    decreaseKey(i, Integer.MIN_VALUE);

    // Extract the minimum element (which is now at the root)
    extractMin();
}

Test:-

printHeapArray(heap);
heap.delete(2);
System.out.println("Heap array after delete:");
printHeapArray(heap);

Output:-
1 3 2 15 5 4 45
Heap array after delete:
1 3 4 15 5 45

Time complexity: O(log n)

Build Heap

Given a random array, rearrange its elements to form a min Heap.
Input array: {10, 5, 20, 2, 4, 8}

       10
      /  \
     5    20
    / \   /
   2   4  8 

Output array: {2, 4, 8, 5, 10, 20}

       2
      /  \
     4    8
    / \   /
   5  10 20 

Input array: {30, 20, 10}

  30
 /  \
20  10

Output array: {10, 20, 30}

  10
 /  \
20  30

To transform a random array into a min heap, you can use the “Build Heap” algorithm, which constructs a heap in O(n) time. Steps to Build a Min Heap:

1. Start from the Last Non-Leaf Node: In a complete binary tree, the last non-leaf node is at index n/2 - 1, where n is the number of elements in the array. Start heapifying from this index and move upwards to the root.
2. Heapify Subtrees: For each node, perform the minHeapify operation to ensure the subtree rooted at that node satisfies the min-heap property. This involves comparing the node with its children and swapping if necessary, then recursively heapifying the affected subtree.

public void buildHeap() {
    // Start heapifying from the last non-leaf node and move upwards to the root
    for (int i = (size - 1) / 2; i >= 0; i--) {
        minHeapify(i);
    }
}

Time complexity: O(n)

Test:-

public class MinHeapTest {

    public static void main(String[] args) {
        // Create a MinHeap with capacity of 10
        MinHeap heap = new MinHeap(10);

        // Given random array
        int[] randomArray = {40, 20, 30, 35, 25, 80, 32, 100, 70, 60};

        // Assign the elements to the heap and set the size
        System.arraycopy(randomArray, 0, heap.arr, 0, randomArray.length);
        heap.size = randomArray.length;
        printHeapArray(heap);

        // Build the heap from the random array
        heap.buildHeap();

        // Print the heap array after building the heap
        System.out.println("Heap array after building the heap:");
        printHeapArray(heap);
    }

    // Helper method to print heap array
    private static void printHeapArray(MinHeap heap) {
        for (int i = 0; i < heap.size; i++) {
            System.out.print(heap.arr[i] + " ");
        }
        System.out.println();
    }
}

Heap Sort

Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure. It sorts an array by leveraging the properties of max heaps (or min heaps). If we want to sort the array in increasing order then we use max heap, else we use min heap.

It is based on selection sort which works by repeatedly finding the maximum element from the unsorted part of the array and swapping it with the last unsorted element, thus growing the sorted portion of the array one element at a time. We used to do a linear search to find the maximum elements therefore it takes O(n^2) times. In Heap sort, instead of linear search, we will use the heap data structure to find the maximum element.

Steps for Heap Sort:

1. Build a Max Heap: Convert the input array into a max heap. A max heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. This can be done by calling the buildHeap function on the input array.
2. Extract Elements from the Heap: Repeatedly extract the maximum element from the heap (the root of the heap), and move it to the end of the array. After removing the maximum element, reduce the size of the heap and call heapify to restore the heap property.
3. Repeat the Process: Continue the process of extracting the maximum element and heapifying the reduced heap until all elements are sorted.

Example: Let’s go through an example to sort the array [40, 20, 30, 35, 25, 80, 32, 100, 70, 60] using heap sort.

1. Build a Max Heap: Transform the array into a max heap.

          100
         /    \
        70     80
       /  \   /  \
      40  60 32  30
     /  \  /
    35  25 20

2. Extract Maximum Element: Swap the root 100 with the last element 20 and reduce the heap size. Heapify the reduced heap to maintain the max heap property.

           70
         /    \
        60     80
       /  \   /  \
      40  20 32  30
     /  \  /
    35  25

Array after the first extraction: [70, 60, 80, 40, 20, 32, 30, 35, 25, 100]

3. Repeat the Process: Continue extracting the maximum element and heapifying the reduced heap.

           80
         /    \
        70     32
       /  \   /  \
      40  25 30  20
     /  \ 
    35  60

Array after the second extraction: [80, 70, 32, 40, 25, 30, 20, 35, 60, 100]

           70
         /    \
        40     32
       /  \   /  \
      35  25 30  20
     /  
    60  

Array after the third extraction: [70, 40, 32, 35, 25, 30, 20, 60, 80, 100]

4. Final Sorted Array: After completing all extractions, the sorted array is: [20, 25, 30, 32, 35, 40, 60, 70, 80, 100]

public class MaxHeap {

    int arr[];
    int size;
    int capacity;

    public MaxHeap(int c) {
        arr = new int[c];
        size = 0;
        capacity = c;
    }

    int left(int i) {
        return 2 * i + 1;
    }

    int right(int i) {
        return 2 * i + 2;
    }

    int parent(int i) {
        return (i - 1) / 2;
    }

    // Build max heap from existing array
    public void buildMaxHeap() {
        for (int i = (size - 1) / 2; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    // Heapify a subtree rooted at index i for max heap
    public void maxHeapify(int i) {
        int lt = left(i), rt = right(i);
        int largest = i;
        if (lt < size && arr[lt] > arr[i]) {
            largest = lt;
        }
        if (rt < size && arr[rt] > arr[largest]) {
            largest = rt;
        }
        if (largest != i) {
            swap(arr, i, largest);
            maxHeapify(largest);
        }
    }

    // Helper method to swap elements in the array
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // Heap sort algorithm using max heap
    public void heapSort() {
        buildMaxHeap(); // Build a max heap from the input array
        for (int i = size - 1; i > 0; i--) {
            swap(arr, 0, i); // Move current root to end
            size--; // Reduce the size of the heap
            maxHeapify(0); // Restore the heap property
        }
    }
}

public class HeapSortTest {

    public static void main(String[] args) {
        // Given random array
        int[] randomArray = { 40, 20, 30, 35, 25, 80, 32, 100, 70, 60 };

        // Create a MaxHeap with capacity of the array length
        MaxHeap heap = new MaxHeap(randomArray.length);

        // Assign the elements to the heap and set the size
        System.arraycopy(randomArray, 0, heap.arr, 0, randomArray.length);
        heap.size = randomArray.length;

        System.out.println("Initial Array:");
        printArray(heap.arr);

        // Perform heap sort
        heap.heapSort();

        // Print the sorted array
        System.out.println("Sorted array:");
        printArray(heap.arr);
    }

    // Helper method to print an array
    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output:-

Initial Array:
40 20 30 35 25 80 32 100 70 60
Sorted array:
20 25 30 32 35 40 60 70 80 100

Heap sort can be seen as the improvement of the selection sort. The worst time complexity of the selection sort is O(n^2) whereas the worst time complexity for the heap sort is O(n log n) in all cases which is the best time complexity for any comparison-based sorting. However, the constants hidden in heap sort are higher than merger sort and quick sort. In practice, merge sort and quick sort takes less time compared to heap sort.

PriorityQueue Class in Java

PriorityQueue mainly implements a heap data structure and by default, it implements the min-heap data structure.

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(10);
        pq.add(20);
        pq.add(15);
        System.out.println(pq); // [10, 20, 15]

        System.out.println(pq.peek()); // 10
        // poll() will extract min and heapify
        System.out.println(pq.poll()); // 10

        System.out.println(pq); // [15, 20]
        System.out.println(pq.peek()); // 15 
    }
}

The default implementation is min heap, but if we want to use max heap then we can use Collections.reverseOrder() method.

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

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.add(10);
        pq.add(20);
        pq.add(15);
        System.out.println(pq); // [20, 10, 15]

        System.out.println(pq.peek()); // 20
        // poll() will extract max and heapify
        System.out.println(pq.poll()); // 20

        System.out.println(pq); // [15, 10]
        System.out.println(pq.peek()); // 15
    }
}

Sort a K-Sorted Array

A k-sorted array is an array where each element is at most k positions away from its target position in the sorted array. In other words, an element that is supposed to be at index i in the sorted array can be found anywhere in the range from i-k to i+k in the given array. Problem

Problem Explanation: The task is to sort this k-sorted array efficiently. The key insight is that since each element is at most k positions away from its correct position, we can use a min heap to achieve this.

Input array = {9, 8, 7, 18, 19, 17}
K = 2
Output array = {7, 8, 9, 17, 18, 19}

Input array = {10, 9, 7, 8, 4, 70, 50, 60}
K = 4
Output array = {4, 7, 8, 9, 10, 50, 60, 70}

The naive solution is to use any sorting algorithm that can have the best O(n log n) time complexity. However, it can be done using a min heap in O(n log k) time.

Steps to Sort a K-Sorted Array:

1. Create a Min Heap: Create a min heap of size k+1. This is because at any given point, the minimum element of the unsorted part of the array will be within the first k+1 elements.
2. Insert First k+1 Elements into the Min Heap: Insert the first k+1 elements of the array into the min heap.
3. Extract Min and Insert New Element: For the remaining elements in the array, do the following:
   • Extract the minimum element from the min heap (this is the next element in the sorted array).
   • Insert the next element from the array into the min heap.
4. Extract Remaining Elements from the Heap: After processing all elements of the array, extract the remaining elements from the min heap and place them in the sorted order.

import java.util.Arrays;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 10, 9, 7, 8, 4, 70, 50, 60 };
        int k = 4;
        sortKSortedArray(arr, k);
        System.out.println(Arrays.toString(arr));
        // [4, 7, 8, 9, 10, 50, 60, 70]
    }

    private static void sortKSortedArray(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Store the first k elements in the heap
        for (int i = 0; i <= k; i++) {
            pq.add(arr[i]);
        }

        int index = 0;

        // Add remaining elements
        for (int i = k + 1; i < arr.length; i++) {
            // Extract the min element
            arr[index++] = pq.poll();
            pq.add(arr[i]);
        }

        // Extract remaining elements
        while (!pq.isEmpty()) {
            arr[index++] = pq.poll();
        }
    }
}

Time complexity: O(k+1 log k+1) for inserting first k+1 elements + O(n-k-1 log k) for inserting remaining elements to the heap + O(k log k) for polling remaining elements. So overall it takes O(n log k).

Buy Maximum Items with the Given Sum

Given an array of prices of n items and a sum S, the goal is to determine the maximum number of items you can buy without exceeding the sum S. Example:-

Input array: {1, 12, 5, 111, 200}
Sum = 10
Output: 2 (for 1 & 5)

Input array: {20, 10, 5, 30, 100}
Sum = 35
Output: 3 (for 20, 10 & 5)

Method-1: Using Sorting

Sort all cost array, traverse through the array, and check whether you can pick it or not.

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 1, 12, 5, 111, 200 };
        int sum = 10;
        System.out.println(maxItem(arr, sum));
    }

    private static int maxItem(int[] arr, int sum) {
        Arrays.sort(arr);
        int res = 0;
        for (int i = 0; i < arr.length && sum > 0; i++) {
            sum -= arr[i];
            if (sum >= 0) {
                res++;
            }
        }
        return res;
    }
}

Time complexity: O(n log n).

Method-2: Using Heap

Steps to Solve Using a Min Heap:

1. Create a Min Heap: Create a min heap (PriorityQueue) and insert all elements of the input array into the heap.
2. Initialize Variables:

• Initialize a counter count to keep track of the number of items bought.
• The variable sum already holds the maximum sum allowed.

3. Extract the Minimum and Check Sum: While the heap is not empty and the sum is non-negative, do the following:

• Extract the minimum element from the min heap using pq.poll().
• Subtract this element’s value from sum.
• Check if the new sum is still non-negative. If yes, increment the count.

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 1, 12, 5, 111, 200 };
        int sum = 10;
        System.out.println(maxItem(arr, sum)); // 2
    }

    private static int maxItem(int[] arr, int sum) {
        // Build min heap
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int k : arr) {
            pq.add(k);
        }

        int count = 0;
        while (sum >= 0 && !pq.isEmpty()) {
            sum -= pq.poll();
            if (sum >= 0) {
                count++;
            }
        }

        return count;
    }
}

Time complexity: Building the Min Heap: O(n log n), Polling Elements: O(n log n). Therefore, the overall time complexity of the program is: 𝑂(𝑛 log 𝑛 )

K Largest Elements

For a given array print k largest elements in the array. Problem: 215

Input array = {5, 15, 10, 20, 8}
K = 2
Output = 15 20

Input array = {8, 6, 4, 10, 9}
K = 3
Output = 8 9 10

Steps to Find the K Largest Elements using Min Heap of k size:

1. Build a Min Heap of the first K items. O(k)
2. Traverse from the (K+1)th element: O((n-k) * log k)

• Compare the current element with the top of the heap. If it is smaller than the top, ignore it.
• If it is larger, remove the top element and insert the current element into the Min Heap.

1. Print the contents of the Min Heap. O(k)

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 8, 6, 4, 10, 9 };
        int k = 3;
        kLargest(arr, k);
    }

    private static void kLargest(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            pq.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (arr[i] >= pq.peek()) {
                pq.poll();
                pq.add(arr[i]);
            }
        }
        // display
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

Time complexity: O(k + (n-k) * log k)

K Closest Elements

Given an integer array arr and two integers k and x, return the k closest integers to x in the array. The results should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Input array = {10, 15, 7, 3, 4}
X = 8, K = 2
Output: 7 10

Input array = {100, 80, 10, 5, 70}
X = 2, K = 3
Output: 5 10 70

1. Initialize a Max Heap: Use a PriorityQueue to create a max heap with a custom comparator that prioritizes elements based on their absolute difference from x.
2. Insert the First K Elements: Add the first k elements of the array into the heap along with their absolute differences from x. O(k log k)
3. Iterate Over the Remaining Elements: For each remaining element in the array, calculate its absolute difference from x. If this element’s difference is smaller than the largest difference in the heap (heap’s root), remove the root and add the current element along with its difference to the heap. O((n-k) log k)
4. Collect Results from the Heap: After processing all elements, the heap will contain the k closest elements. Extract all elements from the heap.
5. Sort the Result: Sort the extracted elements in ascending order to get the final sorted list of the k closest elements. O(k log k)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 8, 6, 4, 10, 9 };
        int k = 3;
        int x = 7;
        List<Integer> closestElements = findClosestElements(arr, k, x);
        System.out.println(closestElements); // [6, 8, 9]
    }

    private static List<Integer> findClosestElements(int[] arr, int k, int x) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[1] - a[1]));

        // Insert first k elements
        for (int i = 0; i < k; i++) {
            maxHeap.add(new int[] { arr[i], Math.abs(arr[i] - x) });
        }

        // Process remaining elements
        for (int i = k; i < arr.length; i++) {
            int diff = Math.abs(arr[i] - x);
            if (maxHeap.peek()[1] > diff) {
                maxHeap.poll();
                maxHeap.add(new int[] { arr[i], diff });
            }
        }

        // Collect results
        List<Integer> result = new ArrayList<>();
        while (!maxHeap.isEmpty()) {
            result.add(maxHeap.poll()[0]);
        }

        Collections.sort(result);
        return result;
    }
}

Merge K-Sorted Arrays

Given K-sorted arrays, merge them into a single sorted array. Problem 23

Input arr[ ][ ] = {{10, 20, 30}, {5, 15}, {1, 9, 11, 18}}
Output arr[ ] = {1, 5, 9, 10, 11, 15, 18, 20, 30}

Input arr[ ][ ] = {{5, 20, 30}, {1, 2, 3}}
Output arr[ ] = {1, 2, 5, 20, 30}

The super naive solution is to create an array, put all elements in this array, and then sort the resultant array. Time complexity will be O(nk log nk) where k is the number of input arrays, and n is the maximum number of elements in an array.

The naive solution is to copy the first array to a new array res[ ]. Do the following for the remaining arrays starting from the second array:- merge the current array into res[ ]. Time complexity = O(n + 2n + 3n + … + kn) = O(n k^2)

Efficient approach using Min Heap data structure in O(n*k log k):-

1. Define the HeapNode Class: Create a class HeapNode to store the value, array index, and element index.
2. Initialize the Min Heap: Use a PriorityQueue to create a min heap that orders elements based on their value.
3. Insert the First Element of Each Array: Add the first element from each array to the min heap along with the array index and element index. Calculate the total size of the result array.
4. Process the Heap:

• Extract the smallest element from the heap.
• Add the extracted value to the result array.
• Insert the next element from the same array into the heap if available.

5. Collect and Return Results:

• Continue until the heap is empty.
• Return the result array which contains the merged elements in sorted order.

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {

    static class HeapNode {
        int value;
        int arrayIndex;
        int elementIndex;

        public HeapNode(int value, int arrayIndex, int elementIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
            this.elementIndex = elementIndex;
        }
    }

    public static void main(String[] args) {
        int[][] arr = { { 10, 20, 30 }, { 5, 15 }, { 1, 9, 11, 18 } };
        int[] result = mergeKSortedArrays(arr);
        System.out.println(Arrays.toString(result));
        // [1, 5, 9, 10, 11, 15, 18, 20, 30]
    }

    private static int[] mergeKSortedArrays(int[][] arr) {
        PriorityQueue<HeapNode> minHeap = 
            new PriorityQueue<>(Comparator.comparingInt(a -> a.value));
        int totalSize = 0;

        // Insert the first element of each array into the heap
        for (int i = 0; i < arr.length; i++) {
            if (arr.length > 0) {
                minHeap.add(new HeapNode(arr[i][0], i, 0));
                totalSize += arr[i].length;
            }
        }

        int[] result = new int[totalSize];
        int index = 0;

        // Process the heap
        while (!minHeap.isEmpty()) {
            HeapNode current = minHeap.poll();
            result[index++] = current.value;
            int arrayIndex = current.arrayIndex;
            int elementIndex = current.elementIndex;

            // Insert the next element of the same array into the heap
            if (elementIndex + 1 < arr[arrayIndex].length) {
                minHeap.add(new HeapNode(arr[arrayIndex][elementIndex + 1], 
                   arrayIndex, elementIndex + 1));
            }
        }

        return result;
    }
}

You can also implement the Comparable interface for the HeapNode class and override the compareTo method.

import java.util.Arrays;
import java.util.PriorityQueue;

public class Test {

    static class HeapNode implements Comparable<HeapNode> {
        int value;
        int arrayIndex;
        int elementIndex;

        public HeapNode(int value, int arrayIndex, int elementIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
            this.elementIndex = elementIndex;
        }

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

    private static int[] mergeKSortedArrays(int[][] arr) {
        PriorityQueue<HeapNode> minHeap = new PriorityQueue<>();
        // remaining code
    }
}

The median of a Stream

Array[ ] = {25, 7, 10, 15, 20}
Output: 25 16 10 12.5 15
Problem: 295

Sequence	Median
{25}	25
{25, 7}	(25+7)/2 = 16
{25, 7, 10}	10
{25, 7, 10, 15}	(10+15)/2 = 12.5
{25, 7, 10, 15, 20}	15

arr[ ] = {20, 10, 30, 7}
Output: 20 15 20 15

Sequence	Median
{20}	20
{20, 10}	15
{20, 10, 30}	20
{20, 10, 30, 7}	15

The naive solution is to maintain a temporary sorted array and find the median with this logic:-

if(size %2 != 0) return temp[size/2];
else return (temp[size] + temp[(size-1)/2])/2;

temp[ ] = [ 25 ] size = 1
temp[ ] = [ 7, 25 ] size = 2
temp[ ] = [ 7, 10, 25 ] size = 3
temp[ ] = [ 7, 10, 15, 25 ] size = 4
temp[ ] = [ 7, 10, 15, 20, 25 ] size = 5

Efficient Solution using Heap

We will use 2 containers first container will keep smaller half elements (max heap), and the second container will contain greater half elements (min heap). If there are even elements then we will divide half-half elements, else we will put 1 extra in the first container.

How do we choose min or max heap? In the smaller half, we need the maximum element therefore we will use the max heap, and in the greater half we need the minimum element therefore we will use the min heap. Time complexity: O(n log n).

Steps:

1. Initialize Heaps:

• Max Heap (smallerHalf): Keeps track of the smaller half of numbers.
• Min Heap (greaterHalf): Keeps track of the larger half of numbers.

2. Add the First Element:

• Add the first element to the smallerHalf and print it as the median.

3. Process Each Element: For each new element:

• Add it to the appropriate heap.
• Balance the heaps if necessary.
• Print the median:
• If heaps are equal in size, the median is the average of the roots.
• Otherwise, the median is the root of the larger heap.

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

public class Test {
    public static void main(String[] args) {
        int[] arr = { 25, 7, 10, 15, 20 };
        medians(arr); // Output: 25 16.0 10 12.5 15 
    }

    private static void medians(int[] arr) {
        PriorityQueue<Integer> smallerHalf = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> greaterHalf = new PriorityQueue<>();

        smallerHalf.add(arr[0]);
        System.out.print(arr[0] + " ");

        for (int i = 1; i < arr.length; i++) {
            int x = arr[i];

            if (smallerHalf.size() > greaterHalf.size()) {
                // If the current element is smaller than the max of the smaller half
                if (x < smallerHalf.peek()) {
                    greaterHalf.add(smallerHalf.poll());
                    smallerHalf.add(x);
                } else {
                    greaterHalf.add(x);
                }
                System.out.print(((double) (smallerHalf.peek() + greaterHalf.peek()) / 2) + " ");
            } else {
                // If the current element is less than or equal to the max of the smaller half
                if (x <= smallerHalf.peek()) {
                    smallerHalf.add(x);
                } else {
                    greaterHalf.add(x);
                    smallerHalf.add(greaterHalf.poll());
                }
                System.out.print(smallerHalf.peek() + " ");
            }
        }
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search