হিপ (Heap) মূলত একটি বাইনারি ট্রি (Binary tree)। কমপ্লিট বাইনারি ট্রি (Complete binary tree) যাকে বলে। কমপ্লিট বাইনারি ট্রি এর শেষ লেভেল বাদে বাকি লেভেলের প্রতিটি নোডে সর্বোচ্চ সংখ্যক চাইল্ড নোড থাকে। শুধু শেষ নোড গুলো পূর্ণ নাও হতে পারে তবে এক্ষেত্রে বাম থেকে ডানে নোড গুলো সাজানো থাকে। নিচের চিত্রে একটি বাইনারি হিপ (Heap) দেয়া আছে।
হিপ (Heap) এর প্রকারভেদ
হিপ দুইধরনের হতে পারে। ম্যাক্স হিপ (Max heap) এবং মিন হিপ (Min Heap)। ম্যাক্স হিপের জন্য প্যারেন্ট নোডের (parent node) মান তার ডিসেন্ডেন্টের (descendent) থেকে বড় হবে। অর্থাৎ ট্রিয়ের (tree) রুটে ট্রিয়ের সবথেকে বড় মান টি থাকবে। লেফট চাইল্ডে থাকবে লেফট সাবট্রির সবথেকে বড় মান এবং রাইট সাবট্রিতে রাইট সাবট্রির সবথেকে বড়মান থাকবে। এই শর্ত পূরণ করে আমরা ম্যাক্স হিপ বানাতে পারি। অপর দিকে মিন হিপের জন্য প্যারেন্ট নোডের মান ডিসেন্ডেন্টের থেকে ছোট হবে এবং লেফট চাইল্ডে লেফট সাবাট্রির সবথেকে ক্ষুদ্র মান এবং রাইট চাইল্ডে রাইট সাবট্রির সবথেকে ক্ষুদ্র মান থাকবে।
যদি কোনো হিপ n সংখ্যক ইলিমেন্ট (নোড) থাকে তবে তার উচ্চতা হবে।
হিপ (Heap) ডাটা স্ট্রাকচারটি (Data structure) আমরা কখন ব্যবহার করবো?
ম্যাক্স হিপ এর জন্য ধরা যাক আমাদের কিছু নাম্বার পর্যায়ক্রমে দেয়া হবে। এখন দেয়ার সময় যেকোনো মুহূর্তে আবার জিজ্ঞাসা করা হবে আমাদের এখন পর্যন্ত ম্যাক্সিমাম নাম্বার কত? ধরেন আমরা আমাদের ট্রিতে নাম্বার ঢুকাচ্ছি।
প্রথমেই আমাদেরকে বলা হলো ২ কে ট্রিতে রাখো। আমরা ২ কে প্রথম নোডে রেখে দিলাম। এরপর বলা হলো ৭ কে রাখো। এখন ৭ কে এই মুহূর্তে শেষ নোড বা দ্বিতীয় নোডে রেখে দিলাম। এখন আমাদের ট্রিতে কিছু প্রসেসিং করলাম তারপর জিজ্ঞাসা করা হলো আমাদের ট্রিয়ের সর্বোচ্চ এখন কতো। তখন আমাদের ৭ কে রিটার্ন করতে হবে।
এখন আবার দেয়া হলো ১৯,২৫,২৬। তারপর বলা হলো ট্রিয়ের সকল ইলিমেন্টকে বড় থেকে ছোট রিটার্ন করো। তখন আপনার যথাক্রমে ২৬,২৫,১৯,২ রিটার্ন করতে হবে। আশাকরি বুঝাগেছে। তার মানে আমরা প্রতিবার যেই ইলিমেন্টের মান বা প্রায়োরিটি বেশি তাকেই রিটার্ন করবো।
বাইনারি হিপ (Binary heap) কিভাবে কোড করবো?
বাইনারি হিপের (Binary heap) কোড করার জন্য আমরা ডায়নামিক মেমোরি অ্যালোকেশন ব্যবহার করে করবো (এই পোস্টে C++ STL Vector ব্যবহার করে দেখাবো)। বাইনারি ট্রিতে আমরা কিভাবে ইন্ডেক্সিং করবো? যারা সেগমেন্ট ট্রি এর লেখাটি দেখেছেন তারা হয়তো খেয়াল করেছেন আমাদের লেফট চাইল্ড এর ইনডেক্স এবং রাইট চাইল্ড এর ইনডেক্স ছিল। আমরা এখানেও এ পদ্ধতি ব্যবহার করবো।
সুতরাং আমাদের লেফট চাইল্ড এবং রাইট চাইল্ড উভয়েরই প্যারেন্ট নোড হলো
এই পোস্টে আমরা ১ ভিত্তিক ইন্ডেক্সিং করবো। অর্থাৎ আমাদের শুরুর ইনডেক্স ০ না হয়ে ১ হবে।
আসুন আমরা কিভাবে আমাদের হিপ গঠন করবো তার একটা ভিজুয়াল উপস্থাপন দেখি।
পুনরায় বলি, আমাদের এই সংখ্যাগুলো দেয়া হবে পর্যায়ক্রমিক ভাবে ।
প্রথম ধাপে আমাদের ২ দেয়া হলো। আমরা ট্রিকে রাখার জন্য একটি নোড নিবো। এবং ২ কে রাখবো। নিচের মত করে।
দেখেতে পাচ্ছি আমাদের ২ কে ট্রি এর ১ নং ইনডেক্সে রেখে দিয়েছি।
এরপর, দ্বিতীয় ধাপে আমাদেরকে ৭ ইনপুট দেয়া হবে। ৭ কে রাখার জন্য আমরা ট্রিতে একটি নোড বানাবো যাকে আমরা অ্যারের ২ নং ইনডেক্সে প্রথমে রাখবো। যেহেতু ৭, ট্রিয়ের ২ নং ইনডেক্সে আছে এবং আমাদের ম্যাক্স হিপের শর্তানুসারে প্যারেন্ট নোড সবসময় চাইল্ড থেকে বড় হবে, তাই আমরা দেখবো ৭ তার প্যারেন্ট নোডের থেকে বড় কিনা। এখন আসি, ২ নং ইনডেক্সের প্যারেন্ট ইনডেক্স কত? ২ নং ইনডেক্সের প্যারেন্ট ইনডেক্স হলো সুতরাং আমরা ২ নং ইনডেক্সের ৭ কে ১ নং ইনডেক্সের ২ এর সাথে তুলনা করবো। যেহেতু ২, ৭ থেকে ছোট তাই ৭ কে রুট নোডে সরিয়ে আমরা ২ কে ২ নং নোডে নিয়ে আসবো।
তৃতীয় ধাপে আমাদের ইনপুট দেয়া হবে ১৯। আমরা একইভাবে ১৯কে প্রথমে ট্রি এর ৩ নং ইনডেক্সে রেখে দিবো। এখন আমাদেরকে ১৯ এর সাথে ৩ নং ইনডেক্সের প্যারেন্ট নোড নং ইনডেক্সের সাথে তুলনা করতে হবে। দেখা যাছে ১৯, ৭ এর থেকে বড়। তাই আমাদেরকে জায়গা বদল করে নিতে হবে।
চতুর্থ ধাপে আমরা ২৫ কে ট্রিতে রাখবো। এজন্য প্রথমে ২৫ কে ট্রিয়ের ৪ নং ইনডেক্সে রাখবো প্রথমে। তারপর এর প্যারেন্ট ইনডেক্স নং ইনডেক্সের ইলিমেন্ট ২ এর সাথে ২৫ এর তুলনা করবো। এখানে ২৫ বড়। তাই অবস্থান পরিবর্তন বা SWAP হবে।
আবার ২৫ কে ২ নং ইনডেক্সে নেয়ার পরে দেখতে হবে ২ নং ইনডেক্সের প্যারেন্ট ১ এর চেয়ে ২৫ বড় কিনা। যেহেতু ২৫ বড় তাই আমরা ২৫ কে ১ নং নোডে নিয়ে ১৯ কে ২ নং এ নিয়ে আসবো।
একই পদ্ধতিতে আমরা ২৬ এবং ১৭ কে ইনসার্ট করে নিবো। পরের ১ কে ইনসার্ট করার জন্য আমাদের ৩ নং নোডের সাথে কোনোরূপ অবস্থান পরিবর্তন করতে হবে না। ২৬,১৭,১ কে ইনসার্ট করে নিচের মতো ট্রি পাবো।
এরপর ৯০ কে ইনসার্ট করবো ৮ নং নোড হিসাবে। সুতরাং ৯০ (৮ নং নোড) কে আমরা ৪ নং নোডের চাইল্ড হিসেবে এবং পর্যায়ক্রমে ১ নং ইনডেক্সে নিয়ে যাবো। ৩ কে ৯নং নোড হিসেবে ইনসার্ট করবো যার প্যারেন্টও ৪ নং নোড হবে। এখানে কোন সোয়াপ হবে না। কারণ ৯০ কে সোয়াপ করার পরে ৪ নং নোডে ২৫ থাকবে। যেহেতু ২৫, ৩ এর থেকে বড় তাই এখানে সোয়াপ হবে না।
সবশেষে ৩৬ কে ৫ নং ইনডেক্সের চাইল্ড হিসেবে ঢুকিয়ে নিয়মমতো প্রসেস করবো। সুতরাং আমাদের সর্বশেষ ট্রি নিচের মত দেখা যাবে।
বাইনারি ম্যাক্স হিপ কোড করা (Coding binary max heap in C++)
হিপ কোড করা একেবারেই সহজ। হিপ কোড করতে হলে রিকার্শন নিয়ে ধারনা থাকাটা গুরুত্বপুর্ন। বাইনারি হিপ ইনসার্ট করা খুবই সহজ। যদি নতুন সংখ্যা থাকে তবে তাকে ট্রি অ্যারের শেষের ইনডেক্সের পরে নতুন মেমরি অ্যালোকেট করে বসাই (tree.size() তম ইনডেক্স)। তারপর তারপর রিকার্শন এর মাধ্যমে প্যারেন্ট বের করে রুট পর্যন্ত যাবো, যতক্ষণ পর্যন্ত প্যারেন্ট আমার সংখ্যাটি থেকে বড় না হয় ততক্ষণ পর্যন্ত সোয়াপ করা যেতে থাকবো। যেহেতু ট্রি এর উচ্চতা তাই আমাদের ইনসার্টে সময় লাগবে
আবার যদি ম্যাক্স হিপ থেকে সবচেয়ে বড় সংখ্যা ডিলিট করা দরকার পরে তবে আমরা ট্রিয়ের শেষ সংখ্যাকে রুট নোড (১ নং ইনডেক্স) এ নিয়ে বসাবো। এরপর দেখতে হবে রুটের লেফট চাইল্ড বড় না রাইট চাইল্ড। যেটা বড়ো তার সাথে আমরা আমাদের রুটের সংখ্যাকে তুলনা করবো। যদি রুটের সংখ্যা আমাদের চাইল্ড থেকে বড় হয় তবে সোয়াপ হবে। এভাবে নিচে নামতে থাকবো।
নিচে একটি বাইনারি হিপের (Binary heap) ডিলেশন (Deletion) প্রসেস দেখানো হলো। ট্রি থেকে ৪৪ কে বাদ দেয়া হয়েছে।
C++ কোড
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | /* Sharif Hasan - CSE, PUST Apr 24, 2020 02: 14 PM */ #include<bits/stdc++.h> using namespace std; void heapify_bottom_to_root(vector <int> &tree,int at){ int parent=at/2; if(parent==0) return; if(tree[at]>tree[parent]){ swap(tree[at],tree[parent]); heapify_bottom_to_root(tree,parent); } } void insert(vector <int> &tree,int number){ tree.push_back(number); heapify_bottom_to_root(tree,tree.size()-1); } void heapify_root_to_bottom(vector <int> &tree,int at){ int left=2*at; int right=2*at+1; if(left<tree.size()&&tree[left]>=tree[right]&&tree[left]>tree[at]){ swap(tree[left],tree[at]); heapify_root_to_bottom(tree,left); }else if(right<tree.size()&&tree[right]>tree[left]&&tree[right]>tree[at]){ swap(tree[right],tree[at]); heapify_root_to_bottom(tree,right); } } int pop(vector <int> &tree){ if(tree.size()==1) return -1; int max= tree[1]; tree[1]=tree.back(); tree.erase(tree.end()-1); heapify_root_to_bottom(tree,1); return max; } int top(vector <int> tree){ if(tree.size()==1) return -1; return tree[1]; } /*Main function*/ int main() { vector <int> arr={2,7,19,25,26,17,1,90,3,36}; vector <int> tree(1); int i=1; for(auto a:arr){ insert(tree,a); ++i; } int top=0; while((top=pop(tree))!=-1){ cout<<top<<endl; } return 0; } |
কোডের ব্যাখ্যা
আমরা কোডটিকে লক্ষ করলে দেখতে পাই main() বাদে আমাদের মোট ৫ তা ফাংশন আছে। যথা, insert(),pop(),heapify_bottom_to_root(),heapify_root_to_bottom(),top() এই ফাংশন গুলোদিয়ে আমরা আমাদের ট্রিতে বিভিন্ন অপারাশন করবো।
insert() function
insert() ফাংশন ব্যবহার করে আমরা আমাদের ট্রিতে একটি সংখ্যা ঢুকাতে পারবো। ফাংশনটি আবার দেখি।
1 2 3 4 | void insert(vector <int> &tree,int number){ tree.push_back(number); heapify_bottom_to_root(tree,tree.size()-1); } |
আমাদের insert() ফাংশন দুইটি প্যারামিটার গ্রহণ করে। প্রথম টি একটি vector যার মাঝে আমরা আমাদের ট্রি কে রাখবো। এবং ২নং টি একটি সংখ্যা যাকে আমাদের রাখতে হবে।
আমরা শুরুতেই ট্রি (TREE) এর শেষে আমাদের সংখ্যাটি পুশ করেছি। তারপর পরবর্তি প্রসেস (Swaping) এর জন্য আমরা heapify_bottom_to_root()ফাংশন টি কল করেছি। ফাংশনটি দেখে নিই।
1 2 3 4 5 6 7 8 | void heapify_bottom_to_root(vector <int> &tree,int at){ int parent=at/2; if(parent==0) return; if(tree[at]>tree[parent]){ swap(tree[at],tree[parent]); heapify_bottom_to_root(tree,parent); } } |
এই ফাংশনটি দুইটি প্যারামিটার গ্রহণ করে। একটি আমাদের tree vector এবং আরেকটি কত নং ইনডেক্সে আমরা সংখ্যাটি ঢুকিয়েছি তা। ফাংশনটি দ্বিতীয় লাইনে প্রথমেই আমাদের প্যারেন্ট নোডের ইনডেক্স বের করে নেয়। যেহেতু আমরা ১ ভিত্তিক ইন্ডেক্সিং করছি, তাই প্যারেন্ট নোডের মান শুন্য আসলে বুঝা যাবে বর্তমান নোডই আমাদের শেষ নোড (৩ নং লাইন)। ৮ নং লাইনে দেখেছি বর্তমান নোডের মান তার প্যারেন্টের থেকে ছোট না বড়। বড় হলে সোয়াপ করে নিয়েছি, এবং রিকার্শনের মাধ্যমে পরে বর্তমান নোড হিসেবে প্যারেন্ট নোডকে প্রসেসে দিয়েছি।
insert()এর টাইম কমপ্লেক্সিটি
pop() function
pop() ফাংশন দিয়ে আমরা ট্রি থেকে কোন ইলিমেন্ট বাদ দিতে পারবো। নিচে কোড টি দেখে নেই।
1 2 3 4 5 6 7 8 | int pop(vector <int> &tree){ if(tree.size()==1) return -1; int max= tree[1]; tree[1]=tree.back(); tree.erase(tree.end()-1); heapify_root_to_bottom(tree,1); return max; } |
ফাংশনটি শুধু ১ টি প্যারামিটার নেয়। আমাদের ট্রি কে। ২ নং লাইনে চেক করে দেখা হয়েছে, আমাদের ট্রিয়ের সাইজ ১ কিনা। ট্রি এর সাইজ ১ হলে বুঝাযায় আমাদের ট্রি তে রুট নেই। তারমানে ট্রি খালি। যেহেতু রুট এর ইনডেক্স ১, তাই রুট থাকলে আমাদের ট্রিয়ের সাইজ ২ হতো।
আমরা প্রথমে ট্রি এর রুট ইলিমেন্ট বা সর্বোচ্চ ইলিমেন্ট কে max নামক চলকে নিয়ে নিয়েছি (৩ নং লাইন)। তারপর ট্রিয়ের শেষ ইলিমেন্টকে আমরা রুটে ইলিমেন্টে রেখেছি (৪ নং লাইন)। ৫ নং লাইনে আমরা ট্রিয়ের শেষ উপাদানকে ডিলিট করে দিয়েছি। তারপর রিকারশনের মাধ্যমে আমরা আমাদের ট্রিকে পুনরায় বিন্যাস করেছি। heapify_root_to_bottom() ফাংশনটি সকল প্রভাবিত সাবট্রিকে পুনারায় সজ্জিত করবে। heapify_root_to_bottom() কোডটি দেখি।
1 2 3 4 5 6 7 8 9 10 11 12 | void heapify_root_to_bottom(vector <int> &tree,int at){ int left=2*at; int right=2*at+1; if(left<tree.size()&&tree[left]>=tree[right]&&tree[left]>tree[at]){ swap(tree[left],tree[at]); heapify_root_to_bottom(tree,left); }else if(right<tree.size()&&tree[right]>tree[left]&&tree[right]>tree[at]){ swap(tree[right],tree[at]); heapify_root_to_bottom(tree,right); } } |
২ এবং ৩ নং লাইনে আমাদের বর্তমান নোডের লেফট এবং রাইট চাইল্ড বের করা হয়েছে। ৫ নং লাইনে দেখা হয়েছে লেফট চাইল্ড রাইট চাইল্ড থেকে বড় কিনা একই সাথে লেফট চাইল্ড বর্তমান ইলিমেন্টের থেকে বড় কিনা। যদি সর্ত ঠিক থাকে তবে আমরা বর্তমান নোডকে লেফট নোডের সাথে সোয়াপ করবো। এবং রিকার্শন এর মাধ্যমে লেফট সাব ট্রি ঠিক করবো। অন্যথায় একইরকম শর্ত দিয়ে রাইট সাবট্রিতে কাজ করবো। যখন সোয়াপ হবে না তখন রিকার্শন থেমে যাবে।
pop() এর টাইম কমপ্লেক্সিটি
top() function
এই ফাংশন শুধু রুট নোডের মান রিটার্ন করবে।
এখানে লক্ষণীয়, আমরা কিন্তু ট্রিতে কোন সংখ্যা এত দ্রুত খুঁজে বের করতে পারবো না। এজন্য আমাদের প্রত্যেকটা নোডকেই খুঁজে দেখতে হবে।
শেষ করা উচিত এখন 🙂
হিপ কে আমরা কখনও প্রায়োরিটি কিউ (Priority queue) বলি। কিউ থেকে আমরা জানি, যে আগে আসবে সে আগে বের হয়ে যাবে। কিন্তু প্রায়োরিটি কিউ এর জন্য বিষয়টা অন্যরকম। কে আগে যাবে তা নির্ধারণ হবে কে কত টাকাওয়ালা তার উপর :p । যাইহোক, C++ STL এ priority_queue<> নামে একটা ডাটাস্ট্রাকচার আছে। এটি দিয়েও সহজে হিপ ইমপ্লেমেন্ট করা যাবে।
আজকে যাচ্ছি, বড় লিখা, ভুল চোখে পরলে কমেন্ট অথবা ইনবক্সে জানাতে অনুরুধ করছি। কারও কোনও সমস্যা হলেও জানাতে ভুলবেন না।
প্রচুর বানান ভুল হইছে😶
দুঃখিত, ঠিক করে দেয়ার চেষ্টা করছি।
Jodi time complexity ta bujhano jeto Valo hoto