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

হিপ (Heaps)

সবচেয়ে বড় বা ছোটটা সবসময় চোখের সামনে মেলা থাকে — O(1) স্পিডে উত্তর আর O(log n) স্পিডে আপডেট

insert: O(log n)extract min/max: O(log n)peek min/max: O(1)build: O(n)space: O(n)

ধরুন একটা ভিআইপি (VIP) লাউঞ্জ বা ওয়েটিং রুমের কথা। সেখানে নিয়ম হলো, যে সবচেয়ে বেশি গুরুত্বপূর্ণ বা স্পেশাল, সে সবসময় লাইনের একদম সামনে বসে থাকবে। সে যখন কাজ শেষ করে বেরিয়ে যাবে, তখন বাকিদের ভেতর যে সবচেয়ে বেশি স্পেশাল, সে চোখের পলকে ম্যাজিকের মতো সামনের ওই ফাঁকা চেয়ারটায় এসে বসে পড়বে। এর মাঝে যদি নতুন কেউ লাউঞ্জে ধোকে, সে তার ইম্পর্ট্যান্স অনুযায়ী ভদ্রভাবে লাইনের পেছনে বা মাঝখানে গিয়ে নিজের জায়গা খুঁজে নেবেনন। এটাই হলো হিপ (Heap) — এটা হলো এক ধরনের প্রায়োরিটি কিউ (Priority queue), যেখানে সবচেয়ে ইমার্জেন্সি বা দরকারি জিনিসটা সবসময় হাতের নাগালে থাকে।

বইয়ের ভাষায় বলতে গেলে, হিপ হলো একটা কমপ্লিট বাইনারি ট্রি (complete binary tree) যেটাকে খুব সুন্দর করে একটা সাধারণ অ্যারে (array)-র ভেতর সেভ করে রাখা হয়। এর একটাই কড়া নিয়ম আছে:

মিন-হিপ (Min-Heap): বাপ সবসময় তার বাচ্চাদের চেয়ে ছোট (বা সমান) হবে। ফলে ট্রির একদম মাথায় বা রুটে সবসময় সবচেয়ে ছোট সংখ্যাটা বসে থাকে।
ম্যাক্স-হিপ (Max-Heap): বাপ সবসময় তার বাচ্চাদের চেয়ে বড় (বা সমান) হবে। ফলে রুটে সবসময় সবচেয়ে বড় সংখ্যাটা বসে থাকে।

এই ট্রি-টাকে "কমপ্লিট" বলা হয় কারণ এর প্রতিটা লেভেল একদম কানায় কানায় পূর্ণ থাকে (শুধু শেষের লেভেলটা হয়তো কিছুটা ফাঁকা থাকে, তবে সেটাও বাঁ দিক থেকে প্যাক হয়ে বসে)। এই নিটোল শেপের কারণেই এটিকে পয়েন্টার ছাড়া জাস্ট একটা অ্যারে দিয়ে বানানো যায়: অ্যারের i নম্বর ইনডেক্সে থাকা নোডের বাঁ দিকের বাচ্চা থাকে 2i+1 নম্বরে, ডান দিকের বাচ্চা থাকে 2i+2 নম্বরে, আর তার বাপ থাকে (i-1)//2 নম্বরে।

◈ দেখুন কীভাবে হিপে ডেটা ঢোকানো হয় আর সবচেয়ে বড়/ছোটটাকে বের করে আনা হয়

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

সিফট আপ (Sift Up) — নতুন জিনিস ঢোকানোর পর

হিপে নতুন কোনো মান ঢোকাতে হলে, সেটাকে অ্যারের একদম শেষে (অর্থাৎ ট্রির ফাঁকা জায়গায়) বসিয়ে দেওয়া হয়। এরপর তার বাপের সাথে তার তুলনা হয়। যদি দেখা যায় হিপের নিয়ম ভাঙছে (যেমন মিন-হিপে ছেলে বাপের চেয়ে ছোট হয়ে গেছে), তখন বাপ-ছেলের জায়গা বদল (swap) করা হয়। এটাকে বলে "সিফট আপ (sift up)" করা বা নিচে থেকে ওপরে উঠে আসা। যতক্ষণ না নিয়ম ঠিক হচ্ছে বা সে একদম রুটে পৌঁছাচ্ছে, ততক্ষণ এই বদলাবদলি চলতে থাকে। ট্রির উচ্চতা যেহেতু log n, তাই তাকে সর্বোচ্চ log n বারই লাফাতে হয়।

সিফট ডাউন (Sift Down) — বের করে নেওয়ার পর

হিপের রুট বা মাথায় থাকা ডেটাটাই (সবচেয়ে ছোট বা বড়) আমাদের আসল দরকারি জিনিস। সেটাকে যখন বের করে নেওয়া হয়, তখন রুটের জায়গাটা ফাঁকা হয়ে যায়। এই ফাঁকা জায়গা পূরণের জন্য অ্যারের একদম শেষ সংখ্যাটাকে তুলে এনে রুটে বসিয়ে দেওয়া হয়, যাতে অ্যারের মাঝখানে কোনো গর্ত না থাকে। এরপর শুরু হয় "সিফট ডাউন (sift down)": রুট তার দুই বাচ্চার সাথে নিজেকে মেলায়, যদি নিয়ম ভাঙে তবে যে বাচ্চাটা ছোট (মিন-হিপের ক্ষেত্রে), তাকে টেনে ওপরে তোলে আর নিজে নিচে নেমে যায়। নিয়ম ঠিক হওয়া পর্যন্ত এই ওঠানামা চলতে থাকে — এখানেও স্পিড সর্বোচ্চ O(log n)।

খুব ফাস্ট বা O(n) স্পিডে হিপ বানানো (Build Heap)

n-সংখ্যক ডেটাকে একটা একটা করে হিপে ঢোকালে সময় লাগে O(n log n)। তবে এর একটা জাদুকরী বা স্মার্ট উপায় আছে: পাতা (leaf) নয় এমন একদম শেষের নোডটা (n//2 - 1 নম্বরে থাকে) থেকে শুরু করে পেছন দিকে এক এক করে প্রতিটি নোডের ওপর সিফট ডাউন (sift down) চালানো হয়। অবাক করার ব্যাপার হলো, অঙ্কের হিসাবে এই কাজটায় মোট সময় লাগে মাত্র O(n) — এটাকেই বিখ্যাত হিপিফাই (heapify) অ্যালগরিদম বলা হয়, যা হিপ সর্টে ব্যবহার করা হয়।

দ্রষ্টব্য: খুব মনোযোগ দিয়ে শুনুন, হিপ কিন্তু কোনো ফুল সর্টেড (sorted) বা পুরোপুরি সাজানেন ডেটা স্ট্রাকচার নয় — এখানে শুধু ১০০% গ্যারান্টি দেওয়া যায় যে রুটেই সবচেয়ে বড় বা ছোট সংখ্যাটা আছে। বাকি সংখ্যাগুলো নিজেদের মধ্যে কোনো ফিক্সড সিরিয়ালে থাকে না। আর এই হাফ-সর্টেড থাকার কারণেই একটা হিপ বানাতে O(n log n)-এর বদলে মাত্র O(n) সময় লাগে!