ஒரு binary heap என்பது ஒரு முழுமையான இரண்டு மரம் ஆனது, இது ஒரு வரிசையில் சேமிக்கப்பட்டு heap பண்புஐ பராமரிக்கிறது: ஒரு min-heapஇல், ஒவ்வொரு பெற்றோரும் அவர்களின் குழந்தைகளை விட ≤ ஆகும், எனவே குறைந்தபட்சம் எப்போதும் வேரில் உள்ளது. இது ஒரு அகப்राதிகாரம் வரிசைஐ செயல்படுத்துவதற்கான மান செயல்படுத்தலாக இருக்கிறது.
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
| செயல்பாடு | நேரம் |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| n உருப்படிகளிலிருந்து heap கட்ட | O(n) |
Heap அடுத்து-மிக-முக்கியமான உருப்படியை உடனடியாக வழங்குகிறது, எல்லாவற்றையும் முழுவதுமாக வரிசைப்படுத்தாமல், இது மீண்டும் வரிசைப்படுத்துவதை விட மிகவும் குறைவாக செலவு ஆகும்.
இது அகப்ராதிகார-இயக்கப்பட்ட வழிமுறைகளின் அடித்தளம் மற்றும் "k பெரிய/சிறிய" கேள்விக்கான அடிக்கடி நேர்காணல் கருவியாகும்.