힙 트리 만들기

힙 정렬을 하기 위해선 힙 트리로 구성되어있어야 한다.

힙 트리에는 두가지 종류가 있다.

1) 최소 힙

 - 부모가 자식보다 항상 작은 값을 지닌다. -> 루트값이 최소

 - 내림차순 정렬 : 최소 힙의 루트를 뽑고 남아 있는 트리를 다시 최소 힙 트리로 정렬. 그리고 다시 루트를 뽑고 (반복)

ex)

우선 초기에 정렬되지 않은 배열이 다음과 같이 있다.

null

9

100

2

6

55

87

90

23

57

96

변경 순서는 다음과 같다

null

9

55

2

6

100

87

90

23

57

96

null

9

6

2

55

100

87

90

23

57

96

null

2

6

9

55

100

87

90

23

57

96

null

2

6

9

55

96

87

90

23

57

100

null

2

6

9

23

96

87

90

55

57

100

이로써 최소 힙 트리를 만들 수 있는 배열이 완성됐다.

null

2

6

9

23

96

87

90

55

57

100

2) 최대 힙

 - 부모가 자식보다 항상 큰 값을 지닌다 -> 루트값이 최대

 - 오름차순 정렬 : 최소 힙의 루트를 뽑고 남아 있는 트리를 다시 최대 힙 트리로 정렬. 그리고 다시 루트를 뽑고 (반복)

ex)

위의 예와 똑같은 순서의 정렬되지 않은 배열이다.

null

9

100

2

6

55

87

90

23

57

96

변경 순서는 다음과 같다

null

9

100

2

6

96

87

90

23

57

55

null

9

100

2

57

96

87

90

23

6

55

null

9

100

90

57

96

87

2

23

6

55

null

90

100

9

57

96

87

2

23

6

55

null

100

90

9

57

96

87

2

23

6

55

null

100

90

87

57

96

9

2

23

6

55

null

100

96

87

57

90

9

2

23

6

55

최대 힙 트리를 만들 수 있는 배열이 완성됐다.

null

100

96

87

57

90

9

2

23

6

55

소스코드는 아래와 같다.

static int[] arr = new int[11];

public static void main(String[] args){

arr[1] = 9; arr[2] = 100; arr[3] = 2; arr[4] = 6; arr[5] = 55; arr[6] = 87; arr[7] = 90; arr[8] = 23; arr[9] = 57; arr[10] = 96;

MakeHeapTree();

}

public static void MakeHeapTree(){

int parent = 0;

int child = 0;

Boolean swapChk = true;

while(swapChk){

swapChk = false;

for(int i = arr.length-1; i>=2; i--){

parent = i/2;

child = i;

if( arr[parent] > arr[child] ) // 부등호의 방향 : 최소힙(>), 최대힙(<)

{

swap(parent, child);

swapChk = true;

}

}

}

}

public static void swap(int parent, int child){

int temp = arr[parent];

arr[parent] = arr[child];

arr[child] = temp;

}