6.HeapSort - C++

6.HeapSort - C++

#include <iostream>

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

// 0부터 시작하는 배열을 1부터 시작하는 힘모양으로 수정 
void heapify(int arr[], int value, int size) {
    int left = value * 2 + 1;
    int right = value * 2 + 2;
    int max=value;
    if (left<size  &&  arr[left]>arr[max])
        max = left;
    if (right<size  &&  arr[right]>arr[max])
        max = right;
 
    if (max != value) {
        swap(&arr[value], &arr[max]);
        heapify(arr, max, size);
    }
}
 
// 힙을 최대힙 형태로 정렬
void buildHeap(int arr[], int size) {
    int i,j;
    for (i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, i, size);
        for (j = 0; j < size; j++)
            std::cout << arr[j] << " ";
        std::cout << "\n";
    }
}
 
// 트리사이즈를 하나씩 줄여가며 오름차순 힙정렬 실행 
void heapSort(int arr[],int size) {
    int treeSize;
    buildHeap(arr, size);
    for (treeSize = size - 1; treeSize >= 0; treeSize--) {
        swap(&arr[0], &arr[treeSize]);
        heapify(arr, 0,treeSize);
    }
}

int main() {
    int arr[] = { 5,3,4,1,6,10 };
    int size = sizeof(arr) / sizeof(int);
     
    heapSort(arr, size);
    for(int x:arr) std::cout << x << " ";
}

참조 블로그 https://reakwon.tistory.com/43?category=308657