হিপ কিউ একটি বিশেষ ট্রি স্ট্রাকচার যেখানে প্রতিটি পেরেন্ট নোড তার চাইল্ড নোড থেকে ছোট বা সমান হয়। পাইথনে এটি heapq মডিউল দিয়ে ইমপ্লিমেন্ট করা হয়। এটি প্রায়রিটি কিউ বাস্তবায়নে খুব উপকারী যেখানে বেশি ওয়েটেজ বা অগ্রাধিকারযুক্ত আইটেমটি প্রথমে প্রসেস করা হয়।
হিপ তৈরি করা
পাইথনের বিল্ট-ইন heapq লাইব্রেরি ব্যবহার করে হিপ কিউ তৈরি করা যায়। এই লাইব্রেরিতে হিপ ডেটা স্ট্রাকচারের ওপর বিভিন্ন অপারেশন করার জন্য ফাংশন রয়েছে। নিচে সেসব ফাংশনের তালিকা দেওয়া হলো:
- heapify — একটি সাধারণ লিস্টকে হিপে রূপান্তর করে। ফলাফলস্বরূপ হিপে সবচেয়ে ছোট এলিমেন্টটি ইনডেক্স ০-এ চলে যায়। বাকি এলিমেন্টগুলো নিশ্চিতভাবেই সর্টেড থাকে না।
- heappush — বর্তমান হিপ বদলাবেনা হিপে একটি এলিমেন্ট যোগ করে।
- heappop — হিপ থেকে সবচেয়ে ছোট ডেটা এলিমেন্টটি রিটার্ন করে এবং সরিয়ে দেয়।
- heapreplace — হিপের সবচেয়ে ছোট এলিমেন্টকে ফাংশনে দেওয়া নতুন মান দিয়ে রিপ্লেস করে।
হিপ তৈরি করার উদাহরণ
একটি লিস্টের এলিমেন্টগুলো heapify ফাংশন দিয়ে হিপে রূপান্তর করা যায়। নিচের উদাহরণে একটি লিস্ট দিয়ে heapify কল করলে সবচেয়ে ছোট এলিমেন্টটি প্রথম পজিশনে চলে আসে।
উদাহরণ
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)আউটপুট
[1, 3, 5, 78, 21, 45]হিপে এলিমেন্ট যোগ করা
হিপে ডেটা এলিমেন্ট যোগ করলে সেটি সর্বশেষ ইনডেক্সে যুক্ত হয়। তবে যদি নতুন এলিমেন্টটি সবচেয়ে ছোট হয়, তবে আবার heapify কল করলে সেটি প্রথম ইনডেক্সে চলে আসবে। নিচে ৮ সংখ্যাটি যোগ করা হয়েছে।
উদাহরণ
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
heapq.heappush(H, 8)
print(H)আউটপুট
[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]হিপ থেকে এলিমেন্ট মুছে ফেলা
heappop ফাংশন ব্যবহার করে প্রথম ইনডেক্সের এলিমেন্টটি মুছে ফেলা যায়। নিচের উদাহরণে ফাংশনটি সবসময় ইনডেক্স ১-এ থাকা এলিমেন্টটি সরিয়ে দেয় (নোট: আসলে ইনডেক্স ০-ই হিপের রুট)।
উদাহরণ
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
heapq.heappop(H)
print(H)আউটপুট
[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]হিপে এলিমেন্ট রিপ্লেস করা
heapreplace ফাংশন সবসময় হিপের সবচেয়ে ছোট এলিমেন্টটি সরিয়ে নতুন এলিমেন্টটি হিপে উপযুক্ত জায়গায় রাখে।
উদাহরণ
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
heapq.heapreplace(H, 6)
print(H)আউটপুট
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]