[알고리즘] 힙 정렬(Heap Sort)이란?

먼저 힙 정렬에 대해 다루기 전에 "힙"에 대한 이해가 필요합니다.

힙에 대해 알고 싶다면 아래 링크를 참고하시면 도움됩니다.

힙(Heap) 자료구조

---

힙 정렬(Heap Sort)

힙 정렬 알고리즘은 삽입과정 없이 삭제과정만이 이뤄집니다.

최대힙(max heap)을 구현한뒤, 루트 노드를 삭제하여 마지막 노드가 루트 노드가 되어 최대힙의 규칙에 맞게 재구조화 되며 정렬합니다.

 

힙 정렬 알고리즘은 주로 다음과 같은 경우에 유용하게 사용됩니다.

1. 최댓값과 최솟값을 구할 때
2. 최대 k만큼 떨어진 요소들을 정렬할 때

 

힙 정렬 과정

1. 루트 노드가 삭제 되면, 가장 말단의 노드가 루트로 이동합니다.

 

2. 루트 노드자리가 대체 된 후 재구조화 과정을 수행합니다. ( 최대 힙일 경우 예시 )

 

3.더 이상 교환할 노드가 없다면 재구조화 과정은 종료되고, 힙 구조가 완성됩니다.

 

힙 정렬 알고리즘 코드 구현

    public int delete(List<Integer> heap) {
        // 힙 이 비어있으면 0 리턴
        if (heap.size() - 1 < 1) {
            return 0;
        }

        // 삭제할 루트 노드 값 저장
        int deleteNode = heap.get(1);

        // 맨 마지막 자식 노드를 루트 노드와 교체한 뒤, 마지막 값 삭제
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        // 루트에 새로 넣은 노드의 인덱스 정보
        int newRoot = 1;

        while ((newRoot * 2) < heap.size()) {
//            int leftChild = heap.get(newRoot * 2);
//            int rightChild = heap.get(newRoot * 2 + 1);
//            int leftIdx = newRoot * 2;
//            int rightIdx = newRoot * 2 + 1;
            int leftChild = heap.get(newRoot * 2);
            int leftIdx = newRoot * 2;

            //오른쪽 자식이 존재하고 오른쪽 자식이 왼쪽 자식보다 클때 바꿀 자식 오른쪽으로 설정
            if ((newRoot * 2 + 1) < heap.size() && leftIdx < heap.get(newRoot * 2 + 1)) {
                leftChild = heap.get(newRoot * 2 + 1);
                leftIdx = newRoot * 2 + 1;
            }

            // 부모가 더 크면 끝
            if (heap.get(newRoot) > leftChild) {
                break;
            }

            //자식이 더 크면 교환
            int tmp = heap.get(newRoot);
            heap.set(newRoot, leftChild);
            heap.set(leftIdx, tmp);
            newRoot = leftIdx;
        }

        return deleteNode;
    }