Heap / Priority Queue

এমন একটি structure যেখানে সবচেয়ে ছোট item সবসময় উপরে থাকে, আর add বা remove করা দ্রুত হয়।

মূল ধারণা (হাসপাতালের waiting room)

Emergency room-এ কে আগে এসেছে সেটা নয়, বরং যার অবস্থা সবচেয়ে জরুরি তাকে আগে দেখা হয়। Priority queue ঠিক এটাই করে। Min-heap এটি বানানোর একটি কার্যকর উপায়: এমন একটি tree যেখানে প্রতিটি parent তার children-এর চেয়ে ছোট বা সমান। তাই সবচেয়ে ছোট মানটা সবসময় একদম উপরে (root-এ) থাকে এবং সাথে সাথে পাওয়া যায়।

মজার ব্যাপার হলো, tree-টা কোনো pointer ছাড়াই একটা সাধারণ array-তে রাখা হয়। i index-এর item-এর জন্য: children থাকে 2i+1 আর 2i+2-তে, এবং parent থাকে (i-1)/2-তে। নিচের দুটি view আসলে একই data।

Run করে দেখুন

অনুমোদিত: push N, pop, heapify N N N ... (heapify বর্তমান heap-কে ওই array দিয়ে বদলে দেয়)। সর্বোচ্চ 20টি operation এবং 15টি item।

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: সবচেয়ে ছোট মান পড়া সাথে সাথে হয় (O(1))। Push আর pop root থেকে leaf পর্যন্ত একটি path ধরে যায়, তাই প্রায় log₂(n) ধাপ লাগে (O(log n)): 1,000,000 item-এর জন্য মাত্র প্রায় 20টি swap। পুরো array-র heapify লাগে মাত্র O(n)।