힙정렬(heap sort)

 

이진 트리 : 모든 노드의 자식 노드가 2개 이하인 트리구조

 

 

완전 이진트리

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

힙정렬

 

 

 

 

#include <stdio.h>



void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

void heapify(int arr[], int here, int size) {

    int left = here * 2 + 1;

    int right = here * 2 + 2;

    int max=here;

    if (left < size&&arr[left]>arr[max])

        max = left;

    if (right < size&&arr[right]>arr[max])

        max = right;



    if (max != here) {

        swap(&arr[here], &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++)

            printf("%d ", arr[j]);

        printf("\n\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);

    }

}

void printArray(int arr[], int size) {

    int i;

    for (i = 0; i < size; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

int main() {

    int arr[] = { 9,7,6,5,4,3,2,2,1,3 };

    int size = sizeof(arr) / sizeof(int);

     

    heapSort(arr, size);

    printArray(arr, size);

}