Heap sort yana aiki ta nuni?

Question

Accepted Answer

**Heap sort** yana gina **binary heap** daga jiya, sannan yana tsoguwa da alkalami har zuwa ƙarshe don samar da tsarar zane. Yana gudana a cikin **O(n log n)** kuma yana **a waje**.

## Maganar

Max-heap yana ajiye mafi girma akan tushen. Gina heap (O(n)), sannan musanya tushen zuwa ƙarshe, rage heap, da sake-haifyar (sift down) — n lokuta.

## Misali

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Aisance misalin cakilin ya gudana shi a waje ta hanyar sift down a cikin jiya.

## Hadaddun

- **Lokaci:** O(n log n) a duk lokuta. **Sarari:** O(1) a waje.

## Lokacin amfani / abubuwan rashin kyau

Amfani lokacin da aka tabbata **O(n log n)** *da* **O(1) ƙari ƙarfi** (merge sort yana buƙatar O(n); quicksort yana haɗaka O(n²)). Bai **zama** ba kuma yana da rashin kyau cache, don haka a gida ya kasance sannu da sannu mafi jita fiye da quicksort. Heap gida gidansu yana ɗaya **jerin iko** da neman abubuwan top-k.

## Me yasa ya maɗa

Heap sort ita ce kaɗa tsayin aiki wanda zai kasance duka worst-case O(n log n) kuma a waje, yana ba da mahimmanci a cikin iyakawa-ƙarfi ko iyakawa-cikin saita.

Heap tsarin a ƙasa yana da alaaba gida da alheri — jerin iko, Dijkstra algorithm, da streaming top-k.

Yana tabbata tunanin cewa tsarin bayanan daidai yana sa algorithm aje.