힙 정렬 (Heap sort)

힙정렬을 이해하기 위해서는 아래 3개의 정의를 알고 가야함 .

 

 

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

완전 이진 트리 : 데이터가 루트 노드 부터 시작해서 왼쪽 부터 빼곡하게 차있는 트리 형태

힙 (heap) : 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽세 추출 할 수 있는 자료구조 이다.

          최대 힙 : 부모 노드가 자식 노드보다 큰 힙

          최소 힙: 부모 노드가 자식 노드보다 작은 힙

힙 정렬 :  자료구조 '힙(heap)'을 이용하여  최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 
            오름 차순으로 정렬 을 하기 위해서는 최대 힙을 사용하고 , 내림차순은 최소힙을 사용.

 

힙 정렬의 시간 복잡도는 O(N*log N) 이다.

 

 

정렬 순서

 

 

알고리즘

 

오름차순 기준

1. 현재 배열을 최대 힙구조로 만들어준다.

2. 가장 마지막 노드와 루트노드를 교환.

3. 가장 마지막 노드를 제외하고 다시 최대힙구조를 만듦 

4. 위 과정 N번 반복 .

 

 

 코드 

 

#include<iostream>
 
int number = 9;
int heap[9] = { 7 ,6 ,5 ,8 ,3 ,5 ,9 ,1 ,6 };
using namespace std;
int main() {
 
    //힙을 구성
    for (int i = 1; i < number; i++) {
 
        int c = i;
 
        do {
 
            int root = (c - 1) / 2;
            if (heap[root] < heap[c]) {
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            c = root;
        } while (c != 0);
    }
 
    //크기를 줄여가며 반복적으로 힙을 구성
    for (int i = number - 1; i >= 0; i--) {
        int temp = heap[0];
        heap[0] = heap[i];
        heap[i] = temp;
        int root = 0;
        int c = 1;
 
        do {
            c = 2 * root + 1;
            //자식중에 더큰 값을 찾기
            if (c < i - 1 && heap[c] < heap[c + 1]) {
                c++;
            }
 
            // 루트보다 자식이 더 크다면 교환
            if (c < i && heap[root] < heap[c]) {
                temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
 
            root = c;
        } while (c < i);
    }
 
    for (int i = 0; i < number; i++) {
        cout << heap[i] << " ";
    }
 
}

 

 

 

 

 

 

모든 글의 내용은 나동빈님 블로그를 참고 하였습니다.

https://blog.naver.com/ndb796/221228342808