Heaps - 5 মিডিয়াম লেভেল প্রোগ্রামিং সমস্যা ও সমাধান

Heap একটি বিশেষ ধরনের ট্রি-ভিত্তিক ডেটা স্ট্রাকচার যা প্রায়ই priority queue হিসেবে ব্যবহৃত হয়। জাভাতে আমরা PriorityQueue ক্লাস ব্যবহার করে সহজেই Heap তৈরি করতে পারি। এখানে ৫টি মিডিয়াম লেভেল সমস্যা ও তাদের সমাধান দেওয়া হলো।

সমস্যা ১: Kth Largest Element (K-তম বৃহত্তম উপাদান)

সমস্যা বিবরণ

একটি integer array এবং একটি সংখ্যা k দেওয়া আছে। array-এর মধ্যে k-তম বৃহত্তম উপাদানটি খুঁজে বের করতে হবে।

উদাহরণ:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

সমাধান পদ্ধতি

আমরা একটি Min-Heap ব্যবহার করব যার size সর্বোচ্চ k হবে। Heap-এর top-এ সবসময় k-তম বৃহত্তম উপাদানটি থাকবে।

import java.util.PriorityQueue;

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        // Min-Heap তৈরি করা
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            // Heap-এর size k-এর বেশি হলে ছোট উপাদান বাদ দেওয়া
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // Heap-এর top-এ k-তম বৃহত্তম উপাদান থাকবে
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("K-তম বৃহত্তম উপাদান: " + findKthLargest(nums, k));
    }
}

ব্যাখ্যা

আমরা Min-Heap-এ উপাদান যোগ করি।
Heap-এর size k-এর বেশি হলে সবচেয়ে ছোট উপাদানটি সরিয়ে ফেলি।
শেষ পর্যন্ত Heap-এ সবচেয়ে বড় k সংখ্যক উপাদান থাকে এবং top-এ থাকে k-তম বৃহত্তম।

Time Complexity: O(n log k) Space Complexity: O(k)

সমস্যা ২: Merge K Sorted Lists (K-টি সাজানো লিস্ট একত্রিত করা)

সমস্যা বিবরণ

k সংখ্যক sorted linked list দেওয়া আছে। সবগুলোকে একত্রিত করে একটি sorted list তৈরি করতে হবে।

উদাহরণ:

Input: [[1,4,5], [1,3,4], [2,6]]
Output: [1,1,2,3,4,4,5,6]

সমাধান পদ্ধতি

প্রতিটি list-এর প্রথম node Min-Heap-এ রাখব। তারপর সবচেয়ে ছোট node বের করে result-এ যোগ করব।

import java.util.PriorityQueue;

public class MergeKLists {
    // ListNode সংজ্ঞা
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        // val অনুযায়ী Min-Heap তৈরি
        PriorityQueue<ListNode> minHeap =
            new PriorityQueue<>((a, b) -> a.val - b.val);

        // প্রতিটি list-এর প্রথম node যোগ করা
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;

            // পরবর্তী node থাকলে Heap-এ যোগ করা
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);

        ListNode[] lists = {l1, l2};
        ListNode result = mergeKLists(lists);

        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

ব্যাখ্যা

Heap-এ একসাথে সর্বোচ্চ k সংখ্যক node থাকে।
প্রতিবার সবচেয়ে ছোট node বের করে result-এ যোগ করি এবং তার next node Heap-এ ঢোকাই।

Time Complexity: O(N log k) যেখানে N মোট node সংখ্যা Space Complexity: O(k)

সমস্যা ৩: Top K Frequent Elements (সবচেয়ে বেশি বার আসা K-টি উপাদান)

সমস্যা বিবরণ

একটি array দেওয়া আছে। সবচেয়ে বেশিবার appear হওয়া k সংখ্যক উপাদান খুঁজে বের করতে হবে।

উদাহরণ:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]

সমাধান পদ্ধতি

প্রথমে frequency গণনা করব HashMap দিয়ে। তারপর Min-Heap ব্যবহার করে সবচেয়ে বেশি frequency-যুক্ত k উপাদান বের করব।

import java.util.*;

public class TopKFrequent {
    public static int[] topKFrequent(int[] nums, int k) {
        // প্রতিটি উপাদানের frequency গণনা
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // frequency অনুযায়ী Min-Heap
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // result তৈরি করা
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println("Top K উপাদান: " +
            Arrays.toString(topKFrequent(nums, k)));
    }
}

ব্যাখ্যা

HashMap দিয়ে প্রতিটি উপাদানের frequency গণনা করি।
Min-Heap-এ size k রেখে সবচেয়ে কম frequency-যুক্ত entry বাদ দিই।
শেষে Heap-এ সবচেয়ে বেশি frequency-যুক্ত k উপাদান থাকে।

Time Complexity: O(n log k) Space Complexity: O(n + k)

সমস্যা ৪: Find Median from Data Stream (ডেটা স্ট্রিম থেকে মধ্যমা)

সমস্যা বিবরণ

একটি ডেটা স্ট্রিম থেকে ধারাবাহিকভাবে সংখ্যা আসছে। যেকোনো মুহূর্তে এ পর্যন্ত আসা সব সংখ্যার median (মধ্যমা) বের করতে হবে।

উদাহরণ:

addNum(1), addNum(2), findMedian() => 1.5
addNum(3), findMedian() => 2.0

সমাধান পদ্ধতি

দুটি Heap ব্যবহার করব:

Max-Heap (small): ছোট অর্ধেক সংখ্যা রাখবে।
Min-Heap (large): বড় অর্ধেক সংখ্যা রাখবে।

import java.util.*;

public class MedianFinder {
    private PriorityQueue<Integer> small; // Max-Heap
    private PriorityQueue<Integer> large; // Min-Heap

    public MedianFinder() {
        small = new PriorityQueue<>(Collections.reverseOrder());
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // প্রথমে Max-Heap-এ যোগ করি
        small.offer(num);
        // Max-Heap-এর top, Min-Heap-এ স্থানান্তর
        large.offer(small.poll());

        // Balance বজায় রাখা
        if (small.size() < large.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();
        }
        // দুই Heap-এর top-এর গড়
        return (small.peek() + large.peek()) / 2.0;
    }

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

ব্যাখ্যা

small (Max-Heap) সবসময় ছোট অর্ধেক এবং large (Min-Heap) বড় অর্ধেক রাখে।
উভয় Heap-এর size সমান বা small-এ একটি বেশি থাকে।
উপাদান জোড় হলে দুই top-এর গড়, বিজোড় হলে small-এর top median।

Time Complexity: addNum: O(log n), findMedian: O(1) Space Complexity: O(n)

সমস্যা ৫: K Closest Points to Origin (Origin-এর সবচেয়ে কাছের K-টি বিন্দু)

সমস্যা বিবরণ

একটি 2D plane-এ কিছু বিন্দু দেওয়া আছে। Origin (0,0) থেকে সবচেয়ে কাছের k সংখ্যক বিন্দু খুঁজে বের করতে হবে।

উদাহরণ:

Input: points = [[1,3], [-2,2]], k = 1
Output: [[-2,2]]

সমাধান পদ্ধতি

আমরা Max-Heap ব্যবহার করব distance-এর ভিত্তিতে। সবচেয়ে দূরের বিন্দু বাদ দিতে থাকব যতক্ষণ size k না হয়।

import java.util.*;

public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        // distance অনুযায়ী Max-Heap
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1])
        );

        for (int[] point : points) {
            maxHeap.offer(point);
            // size k-এর বেশি হলে সবচেয়ে দূরের বিন্দু বাদ
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        // result তৈরি
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}, {5, 8}, {0, 1}};
        int k = 2;
        int[][] result = kClosest(points, k);

        System.out.println("সবচেয়ে কাছের " + k + " টি বিন্দু:");
        for (int[] point : result) {
            System.out.println(Arrays.toString(point));
        }
    }
}

ব্যাখ্যা

আমরা distance হিসাব করতে x² + y² ব্যবহার করি (square root প্রয়োজন নেই)।
Max-Heap-এ size k রেখে সবচেয়ে দূরের বিন্দু বাদ দিই।
শেষে Heap-এ সবচেয়ে কাছের k বিন্দু থাকে।

Time Complexity: O(n log k) Space Complexity: O(k)

উপসংহার

এই ৫টি সমস্যা থেকে আমরা Heap-এর গুরুত্বপূর্ণ ব্যবহার শিখলাম:

সমস্যা	Heap টাইপ	মূল ধারণা
Kth Largest	Min-Heap	Size k বজায় রাখা
Merge K Lists	Min-Heap	একাধিক list merge
Top K Frequent	Min-Heap	Frequency tracking
Median Finder	দুই Heap	Balanced partition
K Closest Points	Max-Heap	Distance optimization

মূল টিপস:

Kth largest খুঁজতে Min-Heap ব্যবহার করুন।
Kth smallest খুঁজতে Max-Heap ব্যবহার করুন।
জাভাতে PriorityQueue default Min-Heap, Max-Heap-এর জন্য Collections.reverseOrder() বা custom comparator ব্যবহার করুন।

Heap practice চালিয়ে যান এবং সমস্যা সমাধানের দক্ষতা বাড়ান! 🚀