Heap — Yığın Ağacı

#include <stdio.h>
#include <stdlib.h>

#define PARENT(i)  (((i) - 1) / 2)
#define LEFT(i)    (2 * (i) + 1)
#define RIGHT(i)   (2 * (i) + 2)

typedef struct {
    int*  data;       // dinamik dizi
    int   size;       // mevcut eleman sayısı
    int   capacity;   // dizi kapasitesi
} Heap;

Heap* heapOlustur(int kapasite) {
    Heap* h = (Heap*)malloc(sizeof(Heap));
    h->data     = (int*)malloc(kapasite * sizeof(int));
    h->size     = 0;
    h->capacity = kapasite;
    return h;
}

void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

void heapifyUp(Heap* h, int i) {
    while (i > 0 && h->data[i] < h->data[PARENT(i)]) {
        swap(&h->data[i], &h->data[PARENT(i)]);
        i = PARENT(i);
    }
}

void heapEkle(Heap* h, int deger) {
    if (h->size >= h->capacity) {
        h->capacity *= 2;
        h->data = realloc(h->data, h->capacity * sizeof(int));
    }
    h->data[h->size] = deger;     // sona ekle
    heapifyUp(h, h->size);        // yukarı düzelt
    h->size++;
}

void heapifyDown(Heap* h, int i) {
    int enKucuk = i;

    int sol = LEFT(i);
    int sag = RIGHT(i);

    if (sol < h->size && h->data[sol] < h->data[enKucuk])
        enKucuk = sol;
    if (sag < h->size && h->data[sag] < h->data[enKucuk])
        enKucuk = sag;

    if (enKucuk != i) {
        swap(&h->data[i], &h->data[enKucuk]);
        heapifyDown(h, enKucuk);   // alt ağaçta devam
    }
}

int heapCikar(Heap* h) {
    if (h->size <= 0) {
        printf("Heap boş!\n");
        return -1;
    }
    int min = h->data[0];       // kökü kaydet
    h->data[0] = h->data[--h->size]; // son → kök
    heapifyDown(h, 0);           // aşağı düzelt
    return min;
}

void buildMinHeap(Heap* h) {
    // Son yaprak-olmayan düğümden geriye doğru
    for (int i = h->size / 2 - 1; i >= 0; i--) {
        heapifyDown(h, i);
    }
}

void maxHeapifyDown(int arr[], int n, int i) {
    int enBuyuk = i;
    int sol = LEFT(i);
    int sag = RIGHT(i);

    if (sol < n && arr[sol] > arr[enBuyuk])   // > (büyük)
        enBuyuk = sol;
    if (sag < n && arr[sag] > arr[enBuyuk])
        enBuyuk = sag;

    if (enBuyuk != i) {
        swap(&arr[i], &arr[enBuyuk]);
        maxHeapifyDown(arr, n, enBuyuk);
    }
}

void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapifyDown(arr, n, i);
}

void heapSort(int arr[], int n) {
    // Aşama 1: Max-Heap inşa et — O(n)
    buildMaxHeap(arr, n);

    // Aşama 2: Tek tek çıkar — O(n log n)
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);       // max → sona
        maxHeapifyDown(arr, i, 0);   // küçülen heap'i düzelt
    }
}

void heapYazdir(Heap* h) {
    for (int i = 0; i < h->size; i++)
        printf("%d ", h->data[i]);
    printf("\n");
}

int main() {
    printf("=== Min-Heap Demo ===\n\n");

    // ── Tek tek ekleme ──
    Heap* h = heapOlustur(16);
    int degerler[] = {40, 20, 30, 10, 15, 5, 25};

    printf("--- Tek Tek Ekleme ---\n");
    for (int i = 0; i < 7; i++) {
        heapEkle(h, degerler[i]);
        printf("insert(%2d) → ", degerler[i]);
        heapYazdir(h);
    }

    // ── Min çıkarma ──
    printf("\n--- Min Çıkarma ---\n");
    while (h->size > 0) {
        int min = heapCikar(h);
        printf("extractMin=%2d → ", min);
        heapYazdir(h);
    }

    // ── Build-Heap + Heap Sort ──
    printf("\n--- Heap Sort ---\n");
    int arr[] = {40, 20, 30, 10, 15, 5, 25};
    int n = 7;

    printf("Orijinal: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    heapSort(arr, n);

    printf("Sıralı:   ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    free(h->data); free(h);
    return 0;
}

=== Min-Heap Demo ===

--- Tek Tek Ekleme ---
insert(40) → 40
insert(20) → 20 40
insert(30) → 20 40 30
insert(10) → 10 20 30 40
insert(15) → 10 15 30 40 20
insert( 5) → 5 15 10 40 20 30
insert(25) → 5 15 10 40 20 30 25

--- Min Çıkarma ---
extractMin= 5 → 10 15 25 40 20 30
extractMin=10 → 15 20 25 40 30
extractMin=15 → 20 30 25 40
extractMin=20 → 25 30 40
extractMin=25 → 30 40
extractMin=30 → 40
extractMin=40 →
↑ Çıkarma sırası = sıralı! (Heap Sort mantığı)

--- Heap Sort ---
Orijinal: 40 20 30 10 15 5 25
Sıralı:   5 10 15 20 25 30 40