힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

힙 자료구조를 이용하여 정렬.

힙은 완전 이진 트리에 있는 노드 중 키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 만들어진 자료구조이다.

키 값이 가장 큰 노드를 찾기 위한 최대 힙(부모 키 >= 자식 키)을 이용해서 내림차순으로 정렬된 원소를 얻을 수 있고, 키 값이 가장 작은 노드를 찾기 위한 최소 힙(부모 키 <= 자식 키)을 이용해서 오름차순으로 정렬된 원소를 얻을 수 있다.

삭제 연산을 하면 루트 노드의 원소를 삭제하여 반환하는 힙의 특성을 이용해서 원소를 얻고 최대/최소 힙이 되도록 재구성하는 작업을 원소의 수만큼 반복하여 정렬한다.

​

n개의 노드에 대하여 삭제 연산을 하고 힙을 재구성 하는 시간 복잡도는 O(nlog2n)이다.

​

최대 힙 예시)

{57, 16, 41, 2, 50, 6, 32, 27}

​

1. 노드가 8개인 완전 이진 트리를 만든 후 최대 힙으로 구성한다.

           57

           /\

      50    41

      /\      /\

   32 27 16 6

   /

 1

​

2. 힙의 삭제 연산으로 루트 노드를 배열의 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{57}

          50

           /\

      32    41

       /\      /\

    1   27 16  6

​

3. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{50, 57}

          41

           /\

      32    16

       /\     /

     1  27 6

​

4. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{41, 50, 57}

          32

           /\

       27  16

       /\

     1   6

​

5. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{32, 41, 50, 57}

          27

           /\

        6   16

       /

     1

​

6. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{27, 32, 41, 50, 57}

        16

        /\

      6   1

​

7. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{16, 27, 32, 41, 50, 57}

      6

     /

   1

​

8. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 남은 원소들을 최대 힙으로 재구성한다.

{6, 16, 27, 32, 41, 50, 57}

1

​

9. 힙의 삭제 연산으로 루트 노드를 배열의 남은 마지막 자리에 저장하고 힙이 공백이 되었으므로 종료한다.

{1, 6, 16, 27, 32, 41, 50, 57}

​

프로그램 작성)

package test;

class Sort {
	public void heapSort(int[] a) {
		makeHeap(a, a.length); 
		
		for(int i = a.length-1; i>0; i--) {
			swap(a, 0, i);
			
			// 교환 후 최대힙 재구성
			makeHeap(a, i); 
		}
	}
	
	public void makeHeap(int[] a, int num) {
		for(int i=1; i<num; i++) { 
			int child = i; 
			
			while(child > 0) { 
				int parent = (child-1)/2; 
				
				if(a[child] > a[parent]) { 
					swap(a, parent, child);
				} 
				
				child = parent; 
			} 
		}
	}
	
	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.heapSort(a);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)