[Algorithm] Heap Sort

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;

void heapify(int* a, int pos, int size)
{
    int l = pos * 2 + 1;
    int r = pos * 2 + 2;
    int mx_idx = pos;

    if (l < size && a[l] > a[mx_idx])
        mx_idx = l;
    if (r < size && a[r] > a[mx_idx])
        mx_idx = r;

    if (mx_idx != pos) {
        swap(a[pos], a[mx_idx]);
        heapify(a, mx_idx, size);
    }
}

void buildHeap(int* a, int size)
{
    for (int i = size/2 ; i >= 0; --i) {
        heapify(a, i, size);
    }
}

void heapSort(int* a, int size)
{
    buildHeap(a, size);
    for (int i = size - 1; i >= 0; --i) {
        swap(a[0], a[i]);
        heapify(a, 0, i);
    }
}

int main()
{
    int a[8] = { 1,5,3,7,8,6,2,4 };
    heapSort(a, 8);
    for (int i = 0; i < 8; ++i) {
        printf("%d ", a[i]);
    }
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.