র্যান্ডমাইজড হিপ#
র্যান্ডমাইজড হিপ হলো একটি হিপ যা র্যান্ডমাইজেশন ব্যবহার করে সব অপারেশন প্রত্যাশিত লগারিদমিক সময়ে সম্পাদন করতে পারে।
একটি মিন হিপ হলো একটি বাইনারি ট্রি যেখানে প্রতিটি ভার্টেক্সের মান তার চাইল্ডদের মানের চেয়ে কম বা সমান। তাই ট্রি-র সর্বনিম্ন সবসময় রুট ভার্টেক্সে থাকে।
ম্যাক্স হিপ একইভাবে সংজ্ঞায়িত করা যায়: কম-কে বেশি দ্বারা প্রতিস্থাপন করে।
একটি হিপের ডিফল্ট অপারেশনগুলো হলো:
- একটি মান যোগ করা
- সর্বনিম্ন বের করা
- সর্বনিম্ন সরানো
- দুটি হিপ মার্জ করা (ডুপ্লিকেট না মুছে)
- একটি ইচ্ছামতো উপাদান সরানো (যদি ট্রি-তে এর অবস্থান জানা থাকে)
একটি র্যান্ডমাইজড হিপ একটি খুব সরল ইমপ্লিমেন্টেশন দিয়ে এই সব অপারেশন প্রত্যাশিত $O(\log n)$ সময়ে সম্পাদন করতে পারে।
ডেটা স্ট্রাকচার#
আমরা সরাসরি বাইনারি হিপের স্ট্রাকচার বর্ণনা করতে পারি:
struct Tree {
int value;
Tree * l = nullptr;
Tree * r = nullptr;
};ভার্টেক্সে আমরা একটি মান সংরক্ষণ করি। এছাড়াও বাম এবং ডান চাইল্ডের পয়েন্টার আছে, যেগুলো null-এ পয়েন্ট করে যদি সংশ্লিষ্ট চাইল্ড না থাকে।
অপারেশন#
দেখা কঠিন নয় যে সব অপারেশন একটি একক অপারেশনে নামিয়ে আনা যায়: দুটি হিপকে একটিতে মার্জ করা। প্রকৃতপক্ষে, হিপে একটি নতুন মান যোগ করা সেই মানের একটি একক ভার্টেক্স বিশিষ্ট হিপের সাথে হিপ মার্জ করার সমতুল্য। সর্বনিম্ন খুঁজতে কোনো অপারেশনই লাগে না — সর্বনিম্ন সহজভাবে রুটের মান। সর্বনিম্ন সরানো রুট ভার্টেক্সের বাম এবং ডান চাইল্ড মার্জ করার ফলাফলের সমতুল্য। এবং একটি ইচ্ছামতো উপাদান সরানোও একই রকম। আমরা ভার্টেক্সের চাইল্ডদের মার্জ করি এবং ভার্টেক্সটিকে মার্জের ফলাফল দ্বারা প্রতিস্থাপন করি।
তাই আমাদের আসলে শুধু দুটি হিপ মার্জ করার অপারেশন ইমপ্লিমেন্ট করতে হবে। অন্য সব অপারেশন সহজেই এই অপারেশনে নামিয়ে আনা যায়।
ধরি দুটি হিপ $T_1$ এবং $T_2$ দেওয়া আছে। স্পষ্ট যে এদের প্রতিটির রুটে তার সর্বনিম্ন আছে। তাই ফলাফল হিপের রুট হবে এই দুটি মানের মধ্যে ছোটটি। তাই আমরা দুটি মান তুলনা করি এবং ছোটটিকে নতুন রুট হিসেবে ব্যবহার করি। এখন নির্বাচিত ভার্টেক্সের চাইল্ডদের বাকি হিপের সাথে সংযুক্ত করতে হবে। এর জন্য আমরা একটি চাইল্ড নির্বাচন করি এবং বাকি হিপের সাথে মার্জ করি। এভাবে আবার দুটি হিপ মার্জ করার অপারেশন পাই। শীঘ্র বা পরে এই প্রক্রিয়া শেষ হবে (ধাপের সংখ্যা দুটি হিপের উচ্চতার যোগফল দ্বারা সীমাবদ্ধ)।
গড়ে লগারিদমিক কমপ্লেক্সিটি অর্জন করতে, আমাদের দুটি চাইল্ডের মধ্যে একটি বেছে নেওয়ার পদ্ধতি নির্দিষ্ট করতে হবে যেন গড় পাথের দৈর্ঘ্য লগারিদমিক হয়। অনুমান করা কঠিন নয় যে আমরা এই সিদ্ধান্ত র্যান্ডমলি নেব। তাই মার্জ অপারেশনের ইমপ্লিমেন্টেশন নিম্নরূপ:
Tree* merge(Tree* t1, Tree* t2) {
if (!t1 || !t2)
return t1 ? t1 : t2;
if (t2->value < t1->value)
swap(t1, t2);
if (rand() & 1)
swap(t1->l, t1->r);
t1->l = merge(t1->l, t2);
return t1;
}এখানে প্রথমে আমরা পরীক্ষা করি কোনো হিপ খালি কি না, তাহলে কোনো মার্জ অ্যাকশন লাগে না।
অন্যথায় t1 হিপটিকে ছোট মানের হিপ বানাই (প্রয়োজনে t1 এবং t2 অদলবদল করে)।
আমরা t1-এর বাম চাইল্ডকে t2-এর সাথে মার্জ করতে চাই, তাই র্যান্ডমলি t1-এর চাইল্ড অদলবদল করি, এবং তারপর মার্জ সম্পাদন করি।
কমপ্লেক্সিটি#
আমরা র্যান্ডম ভেরিয়েবল $h(T)$ প্রবর্তন করি যা রুট থেকে লিফ পর্যন্ত র্যান্ডম পাথের দৈর্ঘ্য নির্দেশ করবে (এজের সংখ্যায় দৈর্ঘ্য)।
স্পষ্ট যে merge অ্যালগরিদম $O(h(T_1) + h(T_2))$ ধাপ সম্পাদন করে।
তাই অপারেশনগুলোর কমপ্লেক্সিটি বুঝতে, আমাদের র্যান্ডম ভেরিয়েবল $h(T)$-এর দিকে তাকাতে হবে।
প্রত্যাশিত মান#
আমরা ধরে নিই $h(T)$-এর প্রত্যাশা হিপের ভার্টেক্স সংখ্যার লগারিদম দ্বারা উপর থেকে আবদ্ধ করা যায়:
$$\mathbf{E} h(T) \le \log(n+1)$$এটি সহজেই আরোহ দ্বারা প্রমাণ করা যায়। ধরি $L$ এবং $R$ হলো রুট $T$-এর বাম এবং ডান সাবট্রি, এবং $n_L$ ও $n_R$ তাদের ভার্টেক্স সংখ্যা ($n = n_L + n_R + 1$)।
নিম্নলিখিতটি আরোহ ধাপ দেখায়:
$$\begin{align} \mathbf{E} h(T) &= 1 + \frac{\mathbf{E} h(L) + \mathbf{E} h(R)}{2} \le 1 + \frac{\log(n_L + 1) + \log(n_R + 1)}{2} \\\\ &= 1 + \log\sqrt{(n_L + 1)(n_R + 1)} = \log 2\sqrt{(n_L + 1)(n_R + 1)} \\\\ &\le \log \frac{2\left((n_L + 1) + (n_R + 1)\right)}{2} = \log(n_L + n_R + 2) = \log(n+1) \end{align}$$প্রত্যাশিত মান অতিক্রম করা#
অবশ্যই আমরা এখনও সন্তুষ্ট নই। $h(T)$-এর প্রত্যাশিত মান সবচেয়ে খারাপ ক্ষেত্র সম্পর্কে কিছু বলে না। এখনও সম্ভব যে একটি নির্দিষ্ট ট্রি-র জন্য রুট থেকে ভার্টেক্সগুলোর পাথ গড়ে $\log(n + 1)$-এর চেয়ে অনেক বেশি।
প্রমাণ করি যে প্রত্যাশিত মান অতিক্রম করার সম্ভাব্যতা সত্যিই খুব কম:
$${\cal P}(h(T) > (c+1) \log n) < \frac{1}{n^c}$$যেকোনো ধনাত্মক ধ্রুবক $c$-এর জন্য।
এখানে $P$ দ্বারা হিপের রুট থেকে লিফ পর্যন্ত সেই পাথগুলোর সেট চিহ্নিত করি যাদের দৈর্ঘ্য $(c+1) \log n$ অতিক্রম করে। লক্ষ্য করুন যে দৈর্ঘ্য $|p|$ বিশিষ্ট যেকোনো পাথ $p$-এর র্যান্ডম পাথ হিসেবে নির্বাচিত হওয়ার সম্ভাব্যতা $2^{-|p|}$। তাই পাই:
$${\cal P}(h(T) > (c+1) \log n) = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$$অ্যালগরিদমের কমপ্লেক্সিটি#
তাই merge অ্যালগরিদম, এবং এর সাথে প্রকাশিত অন্য সব অপারেশন, গড়ে $O(\log n)$-এ সম্পাদন করা যায়।
তদুপরি যেকোনো ধনাত্মক ধ্রুবক $\epsilon$-এর জন্য একটি ধনাত্মক ধ্রুবক $c$ আছে, যেন অপারেশনের $c \log n$-এর বেশি ধাপ প্রয়োজন হওয়ার সম্ভাব্যতা $n^{-\epsilon}$-এর চেয়ে কম (কিছু অর্থে এটি অ্যালগরিদমের সবচেয়ে খারাপ ক্ষেত্রের আচরণ বর্ণনা করে)।