정렬 알고리즘 - 힙 정렬(Heap Sort)

힙 정렬

• 최대 힙 트리나 최소 힙트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

과정

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
3. 삭제되는 요소들(최대값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

내림차순 힙정렬 과정

 

오름차순 힙정렬 과정

 

정렬 알고리즘 시간 복잡도 비교

 

Python Code

def heap_sort(unsorted):
    n = len(unsorted)
    #최대 힙 만들기
    #최소힙은 부등호만 반대로 바꿔주면 됨
    for i in range(1, n):
        child = i
        while child != 0:
            parent = (child-1)//2
            if unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]
            child = parent #최대값이 루트까지 도달 할 수 있도록

    #힙 만들기
    for node in range(n-1, -1, -1):
        #루트 노드와 마지막 노드를 교환
        #값이 큰 순서대로 힙의 끝에 저장됨
        unsorted[0], unsorted[node] = unsorted[node], unsorted[0]
        parent = 0
        child = 1

        # 정렬이 미완료 된 노드들 사이에서
        # 마지막 노드 자리리 보내준 루트 노드를 제외한 가장 큰 값을 찾고
        # 루트 노드 자리로 온 마지막 노드의 자리 찾기
        while child < node:
            child = parent*2 + 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 찾기 위해
            if child < node-1 and unsorted[child] < unsorted[child+1]:
                child += 1
            #마지막 노드 자리로 보낸 루트 노드를 제외한 가장 큰 노드를 루트 자리로 보내기 위한 과정
            if child < node and unsorted[parent] < unsorted[child]:
                unsorted[parent], unsorted[child] = unsorted[child], unsorted[parent]

            parent = child

    return unsorted
    
    if __name__ == '__main__' :
    	arr = list(map(int, input().split()))
    	print(heap_sort(arr))

Java Code

public class Heap
{
	private int[] element; //element[0] contains length
	private static final int ROOTLOC = 1;
	private static final int DEFAULT = 10;

	public Heap(int size) {
		if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
		else {element = new int[DEFAULT+1]; element[0] = 0;}
	}

	public void add(int newnum) {

		if(element.length <= element[0] + 1) {
			int[] elementTemp = new int[element[0]*2];
			for(int x = 0; x < element[0]; x++) {
				elementTemp[x] = element[x];
			}
			element = elementTemp;
		}
		element[++element[0]] = newnum;
		upheap();
	}

	public int extractRoot() {
		int extracted = element[1];
		element[1] = element[element[0]--];
		downheap();
		return extracted;
	}

	public void upheap() {
		int locmark = element[0];
		while(locmark >= 1 && element[locmark/2] > element[locmark]) {
			swap(locmark/2, locmark);
			locmark /= 2;
		}
	}

	public void downheap() {
		int locmark = 1;
		while(locmark * 2 <= element[0])
		{
			if(locmark * 2 + 1 <= element[0]) {
				int small = smaller(locmark*2, locmark*2+1);
				swap(locmark,small);
				locmark = small;
			}
			else {
				swap(locmark, locmark * 2);
				locmark *= 2;
			}
		}
	}

	public void swap(int a, int b) {
		int temp = element[a];
		element[a] = element[b];
		element[b] = temp;
	}

	public int smaller(int a, int b) {
		return element[a] < element[b] ? a : b;
	}
}