হীপ বা প্রায়োরিটি কিউ অ্যালগোরিদম

হীপ (Heap) হচ্ছে এক ধরনের বাইনারি ট্রি। আরো ভালো করে বলতে গেলে কমপ্লিট বাইনারি ট্রি (Complete Binary Tree)। এই ট্রি এর শেষ লেভেল বাদে প্রতিটি লেভেলে সর্বোচ্চ সংখ্যক নোড থাকবে। শুধু শেষ লেভেল্টী পূর্ণ নাও হতে পারে, তবে সেক্ষেত্রেও বাম থেকে ডান দিকে নোড গুলো সাজানো থাকে।

হী দুই রকম হতে পারে, ম্যাক্স হীপ (Max Heap) এবং মিন হীপ (Min Heap)। ম্যাক্স হীপের বৈশিষ্ট্য হচ্ছে কোন নোডে থাকা মান তার যে কোন ডিসেন্ডেন্ট এর থেকে বড় হবে। অর্থাৎ রুটে এই হীপের সবচেয়ে বড় মান থাকবে, তার লেফট চাইল্ডে থাকবে লেফট সাবট্রি এর মাঝের সবচেয়ে বড় মান। এভাবে পুরো হীপ বানানো হয়। ম্যাক্স হীপ বুঝলে, আশাকরি মিন হীপ কি রকম হয় তাও বুঝতে পারছো।

যদি কোন হীপে n সংখ্যক নোড থাকে তাহলে সেই হপের উচ্চতা log(n) হয়। আমরা এই ডেটা স্ট্র্যাকচারটি তখন ব্যবহার করে থাকি যখন আমাদের অনেকগুলো মান এজে এজ আসতে থাকে এবং আমাদের মাঝে মধ্যে সবচেয়ে বড় মানটি দরকার হয়। চাইলে আমাদের বড় মানটি সরিয়ে ফেলতে পারি, ফলে যখন আবারো সবচেয়ে বড় মানের দরকার হয়, তখন এর পরবর্তী বড় মানটী দিতে হয়।

উপরের চিত্রটি একটু খেয়াল করো। এখানে আমাদের সবচেয়ে বড় মান চাইলে ৬ দিতে হবে, এর পর আবারো বড় মান চাইলে ৫ দিতে হবে, এভাবে আরকি। আবার যদি এই দ্বিতীয় চাওয়ার আগে মনে কর ৫.৫ ইনসার্ট হয়, তাহলে কিন্তু আমাদের এই ৫.৫ দিতে হবে, ৫ না।

একটু মনে মনে ভাবো তো, যদি তোমাদের একটি হীপ বানাতে বলি, তাহলে কিভাবে কোড করবে? যদি ভেবে থাকো লিংকড লিস্টের মতো করে পয়েন্টার রেখেন- তাহলে তোমার ভাবনা ঠিক আছে। কিন্তু এর থেকেও সহজ উপায় আছে, যদিও এর অসুবিধাও আছে।

তোমরা যদি আগের মত লেফট চাইল্ড লিংক ও রাইট চাইল্ড লিংক রেখে রেখে কর এবং ডায়ানামিকভাবে মেমোরী অ্যাসাইন কর, তাহলে আগে থেকে আমাদের বড় অ্যারে ডিক্লকেয়ার করার দরকার হয় না। কিন্তু যদি আমরা বড় অ্যারে ডিক্লেয়ার করে করতে চাই তাহলে একটি সহজ উপায় আছে।

উপরে চিত্রে কিভাবে হীপের জন্য অ্যারে ইনডেক্সিং করতে হয় তা দেখালাম। খেয়াল করলে দেখবে, কোণ একটী নোডের ইনডেক্স যদি i হয় তাহলে এর লেফট চাইল্ডের ইনডেক্স হবে 2i এবং এর রাইট চাইল্ডের ইনডেক্স হবে 2i+1. তাহলে দেখো সুন্দর ভাবে পর পর লেভেল-বাই-লেভেল আমাদের ইনডেক্সিং হয়ে যাবে। যদি কোন নোড i থেকে তার প্যারেন্টে নিতে চাও, তাও অনেক সহজ i/2 করেই নিতে পারবে। মনে রাখবে এখানে কিন্তু integer division হচ্ছে।

হীপে ইনসার্ট ক্রয়া খুব সহজ। যদি হীপে ইতোমধ্যে n টি সংখক থাকে তাহলে নতুন সংখ্যা অ্যারের n+1 অবস্থানে বসাতে হবে। এরপর তুমি প্যারেন্ট ব্যবহার করে রুট পর্যন্ত যেতে থাকবে, যদি দেখো প্যারেন্ট তোমার থেকে ছোট থাওলে বদলাবদলি (swapping) করবে, এরকম যতক্ষণ না তোমার প্যারেন্ট তোমার থেকে বড় না হয়, ততক্ষণ এই কাজ করলেই হবে। যেহেতু আমাদের উচ্চতা log(n), সুতরাং আমাদের ইনসার্ট করতে সময় লাগবে O(logn).

যদি ম্যাক্স হতে এর রুট অর্থাৎ সবচেয়ে বড় সংখ্যা ডিলিট করতে চাও, তাহলে যা করতে হবে তা হলো অ্যারের শেষ সংখাকে এনে রুটে বসাতে হবে। এরপর দেখতে হবে তোমার লেফট চাইল্ড বড় না রাইট চাইল্ড বড়। দুইটার মধ্যে যেটি বড় তা যদি আবার তোমার থেকেও বড় হয় তাহলে তার সংগে বদলাবদলি কর এবং এভাবে নিচে নামতে থাকো। এভাবে O(logn) এ আমরা সবচেয়ে বড় সংখ্যাকে ডিলিট করতে পারবো।

একটু চিন্তা করলে তোমরা কোন একোটি নোডকে পরিবর্তন বা ডিলিটও করতে পারবে। কিন্তু একটি জিনিস খেয়াল রাখবে, এখানে কিন্তু কোণ একটি সংখ্যা খুব দ্রুত খুজে পাওয়া সম্ভব না। তোমাকে কোন সংখ্যা খুজতে হলে সবগুলো নোডে যাচাই করতে হতে পারে worst কেইসে।

হীপকে আমরা কখনো কখনো প্রায়োরিটি কিউ (priority queue) বলে থাকি। আমরা কিন্তু এর উদাহরণ হিসেবে বাসের লাইনের কথা জানি। এখন মনেকর, বাসের লাইনে ওরকম আগে আসলে আগে যাবেন না হয়ে কে কত গণ্যমান্য ব্যক্তি তার উপর ভিত্তি করে হবে। তখন এটা হয়ে যাবে প্রায়োরিটি কিউ। যত জন মানুষ আছে তাদের মধ্যে সেই যাবে যার প্রায়োরিটি সবচেয়ে বেশি। এই জিনিসই কিন্তু আমাদের হীপ।

STL এ প্রায়োরিটি কিউ বানিয়ে দেওয়া আছে। নিচের কোড গুলো থেকে কিভাবে STl ব্যবহার করতে হয় তা শিখতে পারবে। তোমরা চাইলে শুধু int না, যে কোন স্ট্র্যাকচারেরও প্রায়োরিটি কিউ বানাতে পার, তবে সেক্ষেত্রে তোমাদের অপারেটর ওভারলোডিং করতে হবে।  আশাকরি কিভাবে অপারেটর ওভারলোডিং করতে হয় তা তুমি জানো।

#include
using namespace std;

priority-queue PQ;  //declare a max heap
PQ.push(4);	//insert
PQ.top();	//maximum element
PQ.pop();	//pop max
PQ.size();	//returns size of heap
PQ.empty();	//returns 1 if the heap is empty

হীপ এবং প্রায়োরিটি কিউ নিয়ে বিস্তারিত পরে অন্য কোন দিন অন্য কোন পোস্টে লিখবো, ইনশাআল্লাহ্‌।।