একটি বাইনারি হিপ হল একটি সম্পূর্ণ বাইনারি ট্রি যা একটি অ্যারেতে সংরক্ষণ করা হয় এবং হিপ সম্পত্তি বজায় রাখে: একটি মিন-হিপে, প্রতিটি অভিভাবক তার সন্তানদের থেকে ≤ থাকে, তাই ন্যূনতম সর্বদা রুটে থাকে। এটি এটিকে একটি অগ্রাধিকার সারির স্ট্যান্ডার্ড বাস্তবায়ন করে তোলে।
1 index: 0 1 2 3 4
/ \ array: [1, 3, 5, 8, 4]
3 5 parent(i) = (i-1)//2
/ \ left(i) = 2i+1
8 4 right(i) = 2i+2
import heapq
h = []
heapq.heappush(h, 5) # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # peek min -> O(1)
heapq.heappop(h) # O(log n) — remove root, sift down -> 1
| অপারেশন | সময় |
|---|---|
| পিক মিন/ম্যাক্স | O(1) |
| পুশ (সন্নিবেশ) | O(log n) |
| পপ (আহরণ) | O(log n) |
| n আইটেম থেকে হিপ তৈরি করুন | O(n) |
একটি হিপ আপনাকে পরবর্তী-সবচেয়ে-গুরুত্বপূর্ণ আইটেমটি তাৎক্ষণিকভাবে দেয় সবকিছু সম্পূর্ণরূপে সর্টেড রাখা ছাড়াই, যা পুনরায় সর্টিং এর চেয়ে অনেক সাশ্রয়ী।
এটি অগ্রাধিকার-চালিত অ্যালগরিদমের মেরুদণ্ড এবং "k বৃহত্তম/ক্ষুদ্রতম" প্রশ্নগুলির জন্য একটি ঘন ঘন সাক্ষাৎকার সরঞ্জাম।