Heap

Heap, ağaç şeklinde bir veri yapısıdır ve özellikle öncelik kuyruklarında kullanılır. Heap, tam bir ağaçtır ve her düğümün iki çocuğu vardır. Heap, en üst düğümün değeri (kök) daima belirli bir özelliğe göre en küçük veya en büyük değerdir. Bu özellik, "min-heap" veya "max-heap" olarak adlandırılır.

Min-heap'te, her düğümün değeri, çocuklarının değerlerinden küçüktür veya eşittir. Bu, en üst düğümün (kök) değerinin tüm ağacın en küçük değeri olduğu anlamına gelir. Max-heap'te ise, her düğümün değeri, çocuklarının değerlerinden büyük veya eşittir ve en üst düğümün (kök) değeri, tüm ağacın en büyük değeridir.

Heap veri yapısının ana avantajı, bir öncelik kuyruğu olarak kullanılabilecek olmasıdır. Yani, yeni bir eleman eklendiğinde, heap özelliğini koruyarak en yüksek veya en düşük önceliği olan elemanın kolayca alınabilmesini sağlar.

Heap veri yapısı, genellikle sıralama algoritmalarında da kullanılır. Örneğin, heap sıralaması, bir dizi sayıyı sıralamak için heap veri yapısını kullanır. Heap sıralaması, n log n zaman karmaşıklığına sahiptir ve birçok diğer sıralama algoritmasından daha hızlıdır.

Heap veri yapısının dezavantajı, ağacın dengelenmesi gerektiğinde, yani yapının özellikleri korunurken ağaçtaki tüm elemanların yeniden düzenlenmesi gerektiğinde, bu işlemin n log n zaman karmaşıklığına sahip olmasıdır.

Heap Veri Yapısı Kullanım Alanları

Heap veri yapısı, bilgisayar bilimleri ve yazılım mühendisliğinde birçok alanda kullanılmaktadır. Başlıca kullanım alanları şunlardır:

1. Öncelik kuyrukları: Heap veri yapısı, öncelik kuyruklarının uygulanmasında kullanılır. Örneğin, işlemci zamanlaması, iş parçacığı önceliği ve acil durumlar gibi alanlarda öncelik kuyrukları kullanılabilir.
2. Sıralama algoritmaları: Heap veri yapısı, sıralama algoritmalarında kullanılır. Örneğin, heap sıralaması, bir dizi sayıyı sıralamak için heap veri yapısını kullanır.
3. Graf algoritmaları: Heap veri yapısı, graf algoritmalarında kullanılır. Örneğin, en kısa yol veya minimum ağaç gibi problemleri çözmek için kullanılır.
4. Bellek yönetimi: Heap veri yapısı, dinamik bellek yönetiminde kullanılır. Örneğin, C veya C++ gibi dillerde, bellek tahsisi yapmak için malloc() veya new operatörleri kullanılır ve heap veri yapısı bu işlemleri gerçekleştirir.
5. Dosya sıralama: Heap veri yapısı, büyük dosyaların sıralanmasında kullanılır. Örneğin, disk tabanlı sıralama algoritmalarında heap veri yapısı kullanılabilir.
6. Oyunlar: Heap veri yapısı, bilgisayar oyunlarında sıkça kullanılır. Örneğin, yapay zeka oyuncuları veya haritaların oluşturulması gibi konularda heap veri yapısı kullanılabilir.

Max Heap

Max heap, bir heap veri yapısı türüdür ve herhangi bir düğümün ebeveyninden büyük veya eşit olduğu bir tam ağaçtır. Bu nedenle, en büyük öğe kök düğümdedir. Max heap ayrıca, tüm alt ağaçları da max heap olan bir öncelik kuyruğu olarak kullanılabilir.

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

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

void heapify(int arr[], int n, int i) {
    int largest = i; // en büyük eleman
    int l = 2 * i + 1; // sol çocuk
    int r = 2 * i + 2; // sağ çocuk

    // sol çocuk en büyükse
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // sağ çocuk en büyükse
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // root en büyük değilse
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

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

void printHeap(int arr[], int n) {
    int i;
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    buildHeap(arr, n);

    printf("Max heap: ");
    printHeap(arr, n);

    return 0;
}

Min Heap

Min heap, bir heap veri yapısı türüdür ve herhangi bir düğümün ebeveyninden küçük veya eşit olduğu bir tam ağaçtır. Bu nedenle, en küçük öğe kök düğümdedir. Min heap ayrıca, tüm alt ağaçları da min heap olan bir öncelik kuyruğu olarak kullanılabilir.

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

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

void heapify(int arr[], int n, int i) {
    int smallest = i; // en küçük eleman
    int l = 2 * i + 1; // sol çocuk
    int r = 2 * i + 2; // sağ çocuk

    // sol çocuk en küçükse
    if (l < n && arr[l] < arr[smallest])
        smallest = l;

    // sağ çocuk en küçükse
    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    // root en küçük değilse
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

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

void printHeap(int arr[], int n) {
    int i;
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    buildHeap(arr, n);

    printf("Min heap: ");
    printHeap(arr, n);

    return 0;
}

Bu kod, verilen dizi üzerinde bir min heap oluşturur ve ardından bu heap'i ekrana yazdırır.