1. 힙정렬의 정의


힙이란 무엇인가?  힙은 쌓아놓음. 쌓아놓은 더미의 뜻의 단어이다.


선택정렬을 응용한 알고리즘인 힙정렬은 힙의 특성을 이용해서 정렬을 수행한다.


힙은 부모의값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리이다.

이때 부모의 값이 자식보다 항상 작아도 힙이라고한다.(부모와 자식요소의 관계만 일정하면 된다)


부모와 자식관계는 항상 부모의값 >= 자식의값이다. 

따라서 힙의 가장 위쪽에 있는 루트가 가장 큰값이 된다.


힙에서 부모와 자식 관계는 일정하지만 형제사이의 대소관계는 일정하지 않다.



2. 트리의 개념


트리의 가장 윗부분을 루트(root)라고 한다. 그리고 요소의 상하관계를 부모(parent)와 자식(child)이라고 한다. 자식 간의 관계는 형제(sibling)이라고 한다.

완전이진트리란 트리의 한 종류를 말한다. 사람도 유전적인 특징에 의해 분류하는 것 처럼 트리의 종류도 여러가지다. 완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전' 이라는 말은 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻이다. 그리고 '이진'이라는 말은 부모가 가질 수 있는 자식의 개수는 최대 2개다 라는 의미이다.


힙의 요소를 배열에 저장하는 과정은 다음 그림과 같다. 가장 위쪽부터 a[0]에 넣고 한단계 아래요소를 왼쪽부터 오른쪽으로 인덱스의 값을 1씩 늘리면서 배열의 각 요소에 힙의 요소를 대입한다.






이 과정을 거치면 부모와 자식의 인덱스 사이에 관계가 성립한다.


1. 부모는 a[(i-1)/2]

2. 왼쪽 자식은 a[i*2+1]

3. 오른쪽 자식은 a[i*2+2]


a[1] 을 저 공식에 대입해보면 부모는 a[0] 왼쪽 자식은 a[3] 8 , 오른쪽 자식은 a[4] 3 이 된다.



3. 힙정렬의 특징


가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘이다.

힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 된다.

힙정렬은 선택정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰값을 구해야 한다.

다시 말해 힙으로 구성된 10개의 요소에서 가장 큰값을 없애면 나머지 9개의 요소 중에서 가장 큰값을 루트로 정해야한다.

따라서 나머지 9개의 요소로 만든 트리도 힙의 형태를 유지할 수 있도록 재구성해야 한다.



힙에서 루트인 10을 꺼낸다. 비어있는 루트 위치로 힙의 마지막 요소(1)을 옮긴다. 이때 1 이외의 요소는 힙 상태를 유지한다.





루트로 이동시킨 1을 올바른 위치로 보내야 한다. 1의 자식은 9와 5인데 힙이 되려면 3개의 값 가운데 가장 큰값이 위쪽에 있어야 한다.

부모의 값>=자식의 값 이라는 힙의 조건을 만족하려면 두 자식을 비교하여 큰 쪽인 9 와 바꾸면 된다.

그러면 1이 왼쪽으로 내려온다.



1의 자식은 8과 3이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 8과 위치를 바꾼다.



1의 자식은 6과 7이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 7과 위치를 바꾼다.


1. 루트를 꺼낸다.

2. 마지막 요소를 루트로 이동시킨다.

3. 자기보다 큰 값을 가지는 자식요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 

이때 자식의 값이 작거나 잎에 다다르면 작업이 종료된다.


4. 힙정렬 알고리즘 흐름


1. 힙의 루트 (a[0])에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꾼다.


2. 가장 큰 값을 a[9]로 옮기면 a[9]는 정렬을 마치게 된다. 

앞에서 살펴본 순서대로 a[0] ~ a[8] 의 요소를 힙으로 만든다. 

그 결과 두번째로 큰 요소인 9가 루트에 위치하게 된다. 

힙의 루트 a[0] 에 있는 가장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꾼다.


3. 두번쨰로 큰 값을 a[8] ~ a[9] 는 정렬을 마치게 된다. 

그런 다음 a[0] ~ a[7] 의 요소를 힙으로 만든다.

그 결과 세번째로 큰 요소인 8이 루트에 위치하게 된다. 

힙의 루트 a[0]에 있는 가장 큰 값인 8을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[7]과 바꾼다.


 

위 설명을 그림으로 표현하면




4. 배열로 힙만들기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package myTest4;
 
import java.util.Scanner;
 
// GregorianCalendar형의 배열을 정렬하는 프로그램
// 1. 자연정렬이 필요한 배열 - 요소의 대소관계를 비교하여 정렬합니다.
public class HeapSort {
    
    // 출력 space1~9 칸수 정의
    static String sp1 = " ", sp2 = "  ", sp3 = "   ";
    static String sp4 = "    ", sp5 = "     ", sp6 = "      ";
    static String sp7 = "       ", sp8 = "        ";
    static String sp9 = "        ";
    
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    static void downHeap(int[] a, int left, int right){
        int temp = a[left];    // 루트
        int child;                    // 큰 값을 가진 노드
        int parent;                // 부모
        
        for(parent = left; parent < (right + 1/ 2; parent = child){
            int cl = parent*2+1;        // 왼쪽 자식
            int cr = cl+1;                // 오른쪽 자식
            child = (cr <= right && a[cr] > a[cl]) ? cr : cl;     // 큰 값을 가진 노드를 자식에 대입
            if(temp >= a[child]){
                break;
            }
            a[parent] = a[child];
        }
        a[parent] = temp;
        
        /* 트리구조 출력하는 소스 시작 */
        int i=0;
        int arrLength  =a.length;
        int k=3;
        int m = 2, n =2;
        int nfloor = 2;
        if(arrLength  > k && arrLength  > 2){
            do{
                // 3,7, 15
                m= m*n; // m=4, m= 8
                k = k+m; // k=7, k= 15
                nfloor++;    // nfloor= 3, nfloor = 4 
            }while(arrLength  > k); // myvalue1 = 10
        }
            
        // if arrLength == 4, 5, 10, 15
        while(i< nfloor-1){ // i=0; nfloor = 4
            String lbranch = "/";
            String rbranch = "\\";
            if(i==0){ // 1층
                System.out.print(sp9+sp9+sp3);
                System.out.println(a[i]);
            }else if(i==1){
                System.out.print(sp9+sp6);
                System.out.print(lbranch);
                System.out.print(sp9+sp3);
                System.out.print(rbranch);
                System.out.println();
                System.out.println(sp9+sp5+a[i]+sp9+sp5+a[i+1]);
            }else// 2층, 3층, 4층
                if(nfloor == 3){
                    nfloor3(a, arrLength, lbranch, rbranch, true);
                }else if(nfloor == 4){
                    nfloor3(a, arrLength, lbranch, rbranch, false);
                    int count = arrLength - 8// 15-7 =8 
                    // 4층 막대기 그리기
                    for(int num=0; num<=count; num++){
                        if(num % 2 == 0){
                            System.out.print(sp6);
                            System.out.print(lbranch);
                        }else{
                            System.out.print(sp3);
                            System.out.print(rbranch);
                        }
                    }
                    System.out.println();
                    
                    // 4층 숫자 출력하기
                    for(int num=8; num<=arrLength; num++){ // 10,9,5,8,3
                        if(num % 2 == 0){
                            System.out.print(sp5);
                            System.out.print(a[num-1]);
                        }else{
                            System.out.print(sp3);
                            System.out.print(a[num-1]);
                        }
                    }
                    System.out.println();
                    System.out.println();
                }
            }
            i++;
        }
        /* 트리구조 출력하는 소스 끝 */
    }
    
    private static void nfloor3(int[] a, int arrLength, String lbranch, String rbranch, boolean flag) {
        // if arrLength 4 4
        int count;
        if(arrLength <= 7){
            count = arrLength - 4;            
        }else{
            count = 3;            
            arrLength = 7;
        }
        // 3층 막대기 출력
        for(int num=0; num<=count; num++){
            if(num % 2 == 0){
                if(num==0){
                    System.out.print(sp7+sp3);
                }else{
                    System.out.print(sp9);
                }
                System.out.print(lbranch);
            }else{
                System.out.print(sp5);
                System.out.print(rbranch);
            }
        }
        System.out.println();
        
        // 3층 숫자 출력
        for(int num=4; num<=arrLength; num++){ // 10,9,5,8,3
            if(num % 2 == 0){
                if(num==4){
                    System.out.print(sp9);
                    System.out.print(a[num-1]);
                }else{
                    System.out.print(sp4);
                    System.out.print(a[num-1]);
                }
            }else{
                System.out.print(sp8);
                System.out.print(a[num-1]);
            }
        }
        if(flag){
            System.out.println();
        }
        System.out.println();
    }
 
    static void heapSort(int[] a, int n){
        for(int i=(n-1)/2; i>=0; i--){    // a[i]~a[n-1]를 힙으로 만들기
            downHeap(a, i, n-1);
        }
        for(int i=n-1; i>0; i--){
            swap(a, 0, i);        // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
            downHeap(a, 0, i-1);        // a[0] ~ a[i-1]을 힙으로 만듭니다.
        }
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("힙 정렬");
        System.out.println("요솟수: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        heapSort(x,nx);    // 배열 x를 힙 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}
cs


결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
힙 정렬
요솟수: 
10
x[0]: 10
x[1]: 9
x[2]: 5
x[3]: 8
x[4]: 3
x[5]: 2
x[6]: 4
x[7]: 6
x[8]: 7
x[9]: 1
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                    9
              /           \
             8             5
          /     \        /     \
        7        3    2        4
      /   \      /
     6    1     10
 
                    8
              /           \
             7             5
          /     \        /     \
        6        3     2        4
      /   \      /
     1    9     10
 
                    7
              /           \
             6             5
          /     \        /     \
        1        3     2        4
      /   \      /
     8    9     10
 
                    6
              /           \
             4             5
          /     \        /     \
        1        3     2        7
      /   \      /
     8    9     10
 
                    5
              /           \
             4             2
          /     \        /     \
        1        3     6        7
      /   \      /
     8    9     10
 
                    4
              /           \
             3             2
          /     \        /     \
        1        5    6        7
      /   \      /
     8    9     10
 
                    3
              /           \
             1             2
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
                    2
              /           \
             1             3
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
                    1
              /           \
             2             3
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
x[9]=10
cs


소스코드와 작업파일 첨부


myTest4.zip

181103 작업파일.pptx



'전체 > 알고리즘' 카테고리의 다른 글

병합정렬  (0) 2018.11.03
퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09

+ Recent posts