একটি Min-Heap হলো এমন একটি complete binary tree, যেখানে প্রতিটি parent node তার children node এর তুলনায় ছোট বা সমান মান ধারণ করে। এই গঠনটির মূল উদ্দেশ্য হলো সবচেয়ে ছোট উপাদানটি দ্রুত খুঁজে পাওয়া। নিচে বিষয়টি বিশদভাবে ব্যাখ্যা করা হলো—
-
মূল (Root) এ থাকে সবচেয়ে ছোট উপাদান — কারণ প্রতিটি স্তরে parent ≤ children হয়, তাই root সর্বদা heap-এর ক্ষুদ্রতম মান।
-
Heap একটি Binary Search Tree নয় — কারণ এটি কেবল heap order মেনে চলে, subtree গুলোকে sorted রাখে না। ফলে বাম বা ডান দিকের node গুলোর মধ্যে ক্রমের কোনো নিশ্চয়তা থাকে না।
-
Arbitrary element খুঁজতে সময় লাগে O(n) — কারণ heap structure অনুযায়ী কেবল root-কে সহজে পাওয়া যায়; অন্য কোনো নির্দিষ্ট element খুঁজতে পুরো tree-টি ট্রাভার্স করতে হতে পারে। এজন্য সময় জটিলতা হয় O(n)।
-
Largest element সর্বদা root এ থাকে না — যেহেতু min-heap এ root-এ থাকে সবচেয়ে ছোট element, তাই সবচেয়ে বড়টি থাকতে পারে tree-এর নিচের কোনো স্তরে।
সুতরাং সঠিক উত্তর গ) — accessing an arbitrary element is an O(n) operation, কারণ heap এর কোনো element এর অবস্থান পূর্বনির্ধারিত নয় এবং সেটি খুঁজতে সম্পূর্ণ heap স্ক্যান করতে হয়।
