Heap என்றால் என்ன மற்றும் அது எவ்வாறு ஒரு অগ்রাধிகার வரிசையை செயல்படுத்துகிறது?

Question

IT Interview Practice · Accepted Answer

ஒரு **binary heap** என்பது ஒரு முழுமையான இரண்டு மரம் ஆனது, இது ஒரு வரிசையில் சேமிக்கப்பட்டு **heap பண்பு**ஐ பராமரிக்கிறது: ஒரு **min-heap**இல், ஒவ்வொரு பெற்றோரும் அவர்களின் குழந்தைகளை விட ≤ ஆகும், எனவே **குறைந்தபட்சம் எப்போதும் வேரில் உள்ளது**. இது ஒரு **அகப்राதிகாரம் வரிசை**ஐ செயல்படுத்துவதற்கான மান செயல்படுத்தலாக இருக்கிறது.

## வரிசை வழிமுறை

```text
       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
```

## செயல்பாடுகள்

```python
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) |

## எப்போது பயன்படுத்த வேண்டும்

- **அகப்ராதிகாரம் மூலம் திட்டமிடல்** (எ.கா. OS பணி அட்ரஸ்).
- **Dijkstra / Prim** குறுகிய பாதை மற்றும் MST வழிமுறைகள்.
- **Top-K** சிக்கல்கள் மற்றும் ஸ்ட்ரீமிங் மধியங்கள்.
- **Heap sort** (இடத்தில் O(n log n)).

## இது ஏன் முக்கியமானது

Heap அடுத்து-மிக-முக்கியமான உருப்படியை உடனடியாக வழங்குகிறது, எல்லாவற்றையும் முழுவதுமாக வரிசைப்படுத்தாமல், இது மீண்டும் வரிசைப்படுத்துவதை விட மிகவும் குறைவாக செலவு ஆகும்.

இது அகப்ராதிகார-இயக்கப்பட்ட வழிமுறைகளின் அடித்தளம் மற்றும் "k பெரிய/சிறிய" கேள்விக்கான அடிக்கடி நேர்காணல் கருவியாகும்.

செயல்பாடு	நேரம்
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
n உருப்படிகளிலிருந்து heap கட்ட	O(n)

வரிசை வழிமுறை

செயல்பாடுகள்

சிக்கலான தன்மை

எப்போது பயன்படுத்த வேண்டும்

இது ஏன் முக்கியமானது

தொடர்புடைய கேள்விகள்