হিপ ও প্রায়োরিটি কিউপড়তে ৬ মিনিট লাগবে

প্রায়োরিটি কিউয়ের প্যাটার্ন (Priority Queue Patterns)

K-তম বড়, K-টা লিস্ট জোড়া লাগানো, টপ-K জনপ্রিয় — সবকিছু একটা ছোট্ট হিপের খেল
push: O(log k)pop: O(log k)space: O(k)

একটা প্রায়োরিটি কিউ (Priority Queue বা PQ) হলো এমন একটা ডেটা স্ট্রাকচার, যার পেছনে আসলে একটা হিপ (heap) কাজ করে: আপনি যেকোনো সিরিয়ালে ডেটা ঢোকাতে পারেন, কিন্তু বের করার সময় সবসময় সবচেয়ে বেশি প্রায়োরিটি বা গুরুত্ব যার, সে-ই আগে বের হবে। এটাকে হাসপাতালের ইমার্জেন্সি বা ট্রায়াজ সিস্টেমের মতো ভাবতে পারেন — রোগীরা যে সিরিয়ালেই আসুক না কেন, পৌঁছানোর সময়ের দিকে না তাকিয়ে সবসময় সবচেয়ে ক্রিটিক্যাল বা মুমূর্ষু রোগীটাকেই আগে ডাক্তার দেখানো হয়।

ইন্টারভিউয়ের প্রশ্নগুলোর জন্য সবচেয়ে বড় ট্রিক হলো: আপনার প্রায় কখনোই পুরো ডেটার সমান সাইজের হিপ লাগে না। আপনার দরকার হয় k সাইজের একটা ছোট হিপ, যেখানে k হলো প্রশ্নে দেওয়া কোনো ছোট শর্ত বা লিমিট। এর ফলে স্পেস বা মেমোরি বেঁচে গিয়ে O(k) হয়ে যায়, আর পুশ/পপ অপারেশনের স্পিড হয় O(log k)।

প্যাটার্ন ১: K-তম সবচেয়ে বড় সংখ্যা (K-th Largest Element)

k সাইজের একটা মিন-হিপ (min-heap) মেইনটেইন করুন। প্রতিটা নাম্বারের জন্য: তাকে হিপে পুশ করুন, তারপর যদি হিপের সাইজ k-এর চেয়ে বড় হয়ে যায়, তবে সবচেয়ে ছোট সংখ্যাটাকে (অর্থাৎ মিন বা মিনিমামটাকে) পপ করে বা বের করে দিন। সব সংখ্যা চেক করা শেষ হলে, হিপের রুট বা মাথায় যে সংখ্যাটা থাকবে (অর্থাৎ ওই ছোট হিপের সবচেয়ে ছোট সংখ্যাটাই), সেটাই হবে আপনার পুরো ডেটার k-তম সবচেয়ে বড় সংখ্যা।

pseudocode
1
2
3
4
5
6
7
8
9
import heapq


def kth_largest(nums, k):
    heap = []  # মিন-হিপ
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]  # রুট বা মাথাই হলো k-তম বড় সংখ্যা

প্রশ্ন হলো, কেন মিন-হিপ? কারণ আপনার দরকার হলো টপ-k সম্ভাব্য লিস্ট থেকে সবচেয়ে ছোট অপশনটাকে ঘাড় ধাক্কা দিয়ে বের করে দেওয়া। আর মিন-হিপের রুট বা মাথা আপনাকে বিনা পরিশ্রমে ঠিক সেই সংখ্যাটাই দেয়।

◈ Explore priority queue

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

প্যাটার্ন ২: K-টা সাজানেন লিস্টকে জোড়া লাগানো (Merge K Sorted Lists)

ধরা যাক আপনাকে k-সংখ্যক সর্টেড বা সাজানেন লিংকড লিস্ট (অথবা অ্যারে) দেওয়া হলো এবং বলা হলো এদের সবাইকে মিলিয়ে বা জোড়া লাগিয়ে একটামাত্র সর্টেড লিস্ট বানাতে। প্রতিটা লিস্টের হেড বা প্রথম সংখ্যাটাকে ওই লিস্টের ইনডেক্স বা সিরিয়াল নাম্বারসহ একটা মিন-হিপে পুশ করুন। এরপর বারবার হিপ থেকে সবচেয়ে ছোট সংখ্যাটাকে পপ করুন, তাকে আপনার ফাইনাল রেজাল্টে জুড়ে দিন, এবং যে লিস্ট থেকে ওকে বের করেছেন, ঠিক সেই লিস্টের পরবর্তী সংখ্যাটাকে হিপে পুশ করুন। ব্যস!

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
def merge_k_sorted(lists):
    result = []
    heap = []  # (value, list_index, element_index)
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, li, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][ei+1], li, ei+1))
    return result
# মোট n-টা সংখ্যা থাকলে সময় লাগবে O(n log k)

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

প্রথমে O(n) সময় নিয়ে একটা ফ্রিকোয়েন্সি ম্যাপ বা হিসাব তৈরি করুন (কে কতবার এসেছে)। তারপর ফ্রিকোয়েন্সি বা সংখ্যাটাকে গুরুত্ব বা প্রায়োরিটি ধরে k সাইজের একটা মিন-হিপ ব্যবহার করুন। ট্রিকটা ঠিক আগের 'K-তম বড় সংখ্যা'র মতোই: হিপের সাইজ k পার হয়ে গেলেই সবচেয়ে কম ফ্রিকোয়েন্সির সংখ্যাটাকে পপ করে বের করে দিন। সবশেষে হিপে যে k-টা সংখ্যা টিকে থাকবে, তারাই হলো সবচেয়ে বেশিবার বা Top-k ফ্রিকোয়েন্সিতে আসা সংখ্যা।

বাকেট সর্ট (Bucket sort) করার আরেকটা বুদ্ধি: ০ থেকে n (ফ্রিকোয়েন্সি হিসেবে ইনডেক্স) পর্যন্ত কিছু বালতি বা বাকেটওয়ালা অ্যারে বানান। এরপর কোন সংখ্যা যতবার এসেছে, তাকে ঠিক সেই নাম্বারের বাকেটে ফেলে দিন। সবশেষে অ্যারের উল্টোদিক (যেহেতু ফ্রিকোয়েন্সি বেশি) থেকে পড়তে শুরু করুন, যতক্ষণ না আপনার পকেটে k-টা সংখ্যা জমছে। এতে সময় এবং স্পেস দুটোই O(n) লাগে।

দ্রষ্টব্য: 'k সাইজের মিন-হিপ'—এই ছোট্ট ট্রিকটা ইন্টারভিউয়ের ডজন ডজন প্রশ্নে ঘুরেফিরে আসে। যখনই প্রশ্নে দেখবেন 'k-তম বড় / সবচেয়ে বেশি আসা top-k / সবচেয়ে কাছের k-টা বের করুন' বলা হয়েছে — সাথে সাথে মাথায় আনবেন: একটা মিন-হিপ নিই, আর সাইজ k পার হলেই ছোটটাকে বের করে দিই। এতে স্পেস লাগে O(k), আর সময় O(n log k)।

Complexity

k সাইজের হিপে পুশ করা
ছোট হিপের ভেতরে ভ্যালুটাকে ওপরের দিকে তোলা (Sift up)
লগারিদমিক (Log k) O(log k)
k সাইজের হিপ থেকে মিন (Min) পপ করা
ছোট হিপের ভেতরে ভ্যালুটাকে নিচের দিকে নামানো (Sift down)
লগারিদমিক (Log k) O(log k)
K-তম বড় বের করা (n-টা সংখ্যা থেকে)
সবগুলো সংখ্যা প্রসেস করতে হয়, কিন্তু হিপের সাইজ কখনোই k পার হয় না
n log k O(n log k)
K-টা লিস্ট জোড়া লাগানো (মোট n-টা সংখ্যা)
মোট n-বার পপ করা লাগে, যার প্রতিটায় সময় লাগে O(log k)
n log k O(n log k)
জায়গা (Space)
অ্যালগরিদমটা শুধু হিপের জন্যই মেমোরি নেয়; ইনপুট ডেটাকে হিসেবে ধরা হয় না
K-টা এন্ট্রি O(k)
Challenge

ছোট কুইজ

আপনাকে এক খাদের ভেতর থেকে অবিরাম ধারায় ১০ লাখ সংখ্যা ছুঁড়ে মারা হচ্ছে। এর মধ্যে থেকে আপনাকে ৩য় সবচেয়ে বড় (3rd largest) সংখ্যাটা খুঁজে বের করতে বলা হলো। আপনি কোন হিপ আর কত সাইজ ব্যবহার করবেন?

পড়া চালিয়ে যান