06 - 힙 정렬(자바편)

🌏 주제 : 배열을 힙으로 만들기

---

힙(Heap)?

힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조입니다. 완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말합니다.

 

1. 힙은 최대힙(Max heap)과 최소힙(Min Heap)으로 나눠집니다. 최대힙은 부모노드의 값이 자식노드들의 값보다 항상 크고, 최소힙은 부모노드의 값이 자식노드의 값보다 항상 작습니다. (위 그림은 최대힙의 예시)
   이러한 성질 때문에 항상 느슨한 정렬상태(반정렬 상태)를 유지합니다.
2. 힙은 중복값을 허용합니다. 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 임으로 중복을 허용합니다.

 

 

 

 

 

 

 

🌏 힙 정렬 예제

---

package Chapter6;

import java.util.Scanner;

public class HeapSort {
	// 배열 요소 a[idx1]과 a[idx2]의 값을 교환
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	// a[left] ~ a[right]를 힙으로 만듬, 맨 앞에 있는 a[left]이외의에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만들기.
	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;
	}
	
	
	// 힙 정렬
	
	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 scan = new Scanner(System.in);
		
		System.out.println("힙 정렬");
		System.out.print("요솟수: ");
		int nx = scan.nextInt();
		int[] x = new int[nx];
		
		for(int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]: ");
			x[i] = scan.nextInt();
		}
		
		heapSort(x,nx);  // 배열 x를 힙 정렬
	
		System.out.println("오름차순으로 정렬했습니다.");
		for(int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]=" + x[i]);
		}

	}

}

-----
힙 정렬
요솟수: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0]=1
x[1]=3
x[2]=4
x[3]=6
x[4]=7
x[5]=8
x[6]=9