Heap Sort

Heap Sort, binary heap data strukturundan istifadə edən effektiv bir sıralama alqoritmidir. Bu alqoritm, əvvəlcə massivdən max-heap yaradır, sonra isə ən böyük elementi götürüb massivın sonuna yerləşdirir.

Heap Sort-un Əsas Xüsusiyyətləri

• Heap Strukturu: Binary heap data strukturundan istifadə edir
• İn-place: Əlavə yaddaş tələb etmir
• Qeyri-stabil: Eyni dəyərə malik elementlərin nisbi sırası dəyişə bilər
• Zəmanətli Performans: Həmişə O(n log n) zaman mürəkkəbliyi

Binary Heap Nədir?

Binary heap, tam binary tree strukturudur və aşağıdakı xassələrə malikdir:

• Max-heap: Hər node öz uşaqlarından böyük və ya bərabərdir
• Min-heap: Hər node öz uşaqlarından kiçik və ya bərabərdir

Heap Sort-un İşləmə Prinsipi

1. Heap Yaratma: Massivdən max-heap yarad
2. Kök Çıxarma: Ən böyük elementi (kök) çıxar
3. Yerləşdirmə: Çıxarılan elementi massivın sonuna yerləşdir
4. Heapify: Yeni köklə heap xassəsini bərpa et
5. Təkrar: Bütün elementlər çıxarılana qədər təkrarla

Heap Sort-un Java-da İmplementasiyası

Koda bax

public class HeapSort {
    
    // Ana sıralama metodu
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // Max-heap yaratmaq (heapify)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Elementləri bir-bir heap-dən çıxarmaq
        for (int i = n - 1; i > 0; i--) {
            // Cari kökü (ən böyük) sona dəyiş
            swap(arr, 0, i);
            
            // Azalmış heap üçün heapify
            heapify(arr, i, 0);
        }
    }
    
    // Subtree-ni heapify etmək
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // Köklə başla
        int left = 2 * i + 1; // Sol uşaq
        int right = 2 * i + 2; // Sağ uşaq
        
        // Sol uşaq köklədən böyükdürsə
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // Sağ uşaq ən böyüklədən böyükdürsə
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // Ən böyük kök deyilsə
        if (largest != i) {
            swap(arr, i, largest);
            
            // Təsir olunan subtree-ni rekursiv heapify et
            heapify(arr, n, largest);
        }
    }
    
    // İki elementin yerini dəyişən köməkçi metod
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // Heap-i çap etmək üçün köməkçi metod
    private static void printHeap(int[] arr, int n) {
        System.out.println("Heap representation:");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    // Test
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        
        System.out.println("Original array:");
        printArray(arr);
        
        // İlk heap-i göstər
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        printHeap(arr, n);
        
        // Sıralama
        heapSort(arr);
        
        System.out.println("\nSorted array:");
        printArray(arr);
    }
    
    // Massivi çap etmək üçün köməkçi metod
    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

Zaman və Yaddaş Mürəkkəbliyi

• Zaman Mürəkkəbliyi:
  • Ən yaxşı hal: O(n log n)
  • Orta hal: O(n log n)
  • Ən pis hal: O(n log n)
• Yaddaş Mürəkkəbliyi: O(1), in-place alqoritm

Heap Sort-un Üstünlükləri və Çatışmazlıqları

Üstünlüklər

• Həmişə O(n log n) zaman mürəkkəbliyi - zəmanətli performans
• In-place alqoritmdir - əlavə yaddaş tələb etmir
• Böyük məlumat dəstləri üçün effektivdir
• Priority queue implementasiyasında istifadə oluna bilər

Çatışmazlıqlar

• Stabil deyil (eyni dəyərli elementlərin sırası dəyişə bilər)
• Praktikada quick sort və merge sort-dan yavaş ola bilər
• Cache performansı yaxşı deyil (random memory access)
• Kiçik massivlər üçün insertion sort daha effektiv ola bilər