힙정렬 (heap sort) 을 간단하게 알아보자.

힙 정렬을 간단하게 설명하면?

최대 힙 트리나 최소 힙 트리를 구성하여 정렬!

1. 힙은 완전 이진트리의 일종입니다. 최댓값과 최솟값을 쉽게 추출할 수 있는 자료구조이며 부가적인 메모리가 필요 없습니다.
2. 내림차순 정렬을 위해서는 최대 힙, 오름차순 정렬을 위해서는 최소 힙을 이용합니다.
3. 먼저 최대 힙을 만들고 그 값을 마지막 인덱스의 값과 스왑 해줍니다. 당연하게도 마지막 인덱스는 최댓값으로 채워집니다.
4. 이제 마지막 인덱스는 제외하고 다시 최대 힙을 만들어 마지막 인덱스(i--) 와의 스왑의 과정을 반복해줍니다. 

 

 

 

구현 과정

import java.util.*;
import java.io.*;
public class Main {

	public static void heapsort(int[] A) {
		for(int i=A.length/2-1; i>=0; i--) {  //부모노드의 수 만큼 부모노드를 기준으로 heapify.
			heapify(A, A.length, i);
		}
		for(int i=A.length-1; i>0; i--) {   //마지막 노드부터 1까지 반복. 0은 아닌 이유 : 0일때는 자기자신과 스왑, heapify함. 낭비. 
			int temp = A[i];      //마지막 노드와 첫번째 노드를 스왑.
			A[i] = A[0];
			A[0] = temp;
			heapify(A, i, 0);    //스왑하고 다시 첫 노드에 최댓값이 놓이도록 루트트리만 heapify. 
		}
	}
	
	public static void heapify(int[] A, int size, int pNode) {
		int parent = pNode;  //parent에 초기의 부모노드 값 저장. 
		int lNode = pNode*2+1;   //왼쪽 자식노드 
		int rNode = pNode*2+2;   //오른쪽 자식노드 
		
		if(size>lNode && A[parent]<A[lNode])   //ex)heapify(A,10,5)인 경우. 자식노드가 전체길이보다 커지니까 말이 안됨. 결국 아래 내용들 실행x, heapify종료.  
			parent = lNode;      //lNode의 위치를 임시로 parent에 저장.
								 //스왑을 바로 안하는 이유: 오른쪽 자식노드가 왼쪽 자식노드보다 큰 경우도 있기 때문.  
		if(size>rNode && A[parent]<A[rNode])  //rNode가 현재 트리 전체의 길이보다 커진 경우에는 실행x. 
			parent = rNode;  //만약 오른쪽자식노드가 parent보다 큰 경우 lNode->rNode로.
		
		if(parent != pNode) {   //parent가 초기값과 다른경우. 즉 자식노드와 바뀐 경우. 
			int temp = A[parent];  //여기서 스왑일어남. 
			A[parent] = A[pNode];
			A[pNode] = temp;
			heapify(A, size, parent); //이제 l or rNode가 parent임. 부모노드의 값이 바꼈으니 최대힙트리를 만족하지 않을 수도 있음. 따라서 새로운 하위의 parent를 기준으로 다시 최대힙.
		}
	}
	
	public static void main(String[] args) {

		int[] heap= {2, 5, 1, 4, 3, 9, 10, 7, 6, 8};
		heapsort(heap);
		
		for(int i=0; i<heap.length; i++) {
			System.out.print(heap[i]+" ");
		}
		}
}

 

시간 복잡도 

• Worst : O(nlogn)
• Average : O(nlogn)
• Best : O(nlogn)