Heap Sort

✅ Heap Sort

Complete Binary Tree
binary tree that adds from left

• 최댓값부터 또는 최솟값부터 정렬
• 전체 정렬하기 ❌
• 가장 큰 값 몇 개만 필요할 때

1. Build complete binary tree from array
   
2. Convert array into heap data structure using heapify
   
   • transfrom heap into max heap
     
   • max heap: parent node always be greater than or equal to child node
     
3. Swap root element of heap(biggest) with the last element of heap
   
4. Remove last element of Heap
   
5. Heapify again
   
6. Recusrive
   
7. Sorted array is reverse(up side down)
   

⭐️ Keyword

max heap, eliminate highest element

✅ Code

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };

    heapSort(array);

    for (int v : array) {
        System.out.println(v);
    }
}

public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    //left node
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //right node
    if (r < n && array[p] < array[r]) {
        p = r;
    }

    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

public static void heapSort(int[] array) {
    int n = array.length;

    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) { //based on parent node, left node, right node
        heapify(array, n, i); //array to heap
    }

    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0); //max heap again after removing biggest element
    }
}

public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

✅ Time complexity

O(N log N)

✅ Space complexity

O(log n) due to recursice call stack

👍🏻 Pros

• in-place algorithm

👎🏻 Cons

• unstable sort

💡 Reference

https://www.geeksforgeeks.org/heap-sort/
https://gyoogle.dev/blog/algorithm/Heap%20Sort.html