목표

• Heap Sort 알고리즘 이해
• Heap Sort 알고리즘 구현
• Heap Sort 알고리즘 특징과 시간복잡도 이해

Heap Sort 알고리즘

• 최대, 최소 힙을 통해서 구현되는 정렬 알고리즘
• 1차원 배열로 쉽게 구현 가능
• 불안정 정렬
• 비교기반 정렬

Heap Sort 알고리즘 구현

1. 힙의 생성 (완전 이진트리)
2. 최대, 최소 힙으로의 변환
   힙으로 변환은 데이터 삽입과 삭제 시 일어남
   
   전체 코드

오류 코드

public void addToSort(int data) {
        maxHeap[++size] = data;
        int current = size;
        while (maxHeap[current] > maxHeap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public int pollToHeap() {
        int max = maxHeap[1];
        maxHeap[1] = maxHeap[size--];
        int current = size;
        while (maxHeap[current] > maxHeap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
        return max;
    }

데이터 입력 시 바로 정렬되고, 출력 시 바로 재정렬되게 구현
기준 위치에 따라 값을 계속 비교하고 스왑만 해주면 된다.

수정코드

public int pollToHeap() { // 최대 힙 제거 후 힙 재조정
        int max = maxHeap[1];
        maxHeap[1] = maxHeap[size--];
        heapify(1);
        return max;
    }

    public void heapify(int i) {
        int leftChild = i * 2;
        int rightChild = (i * 2) + 1;
        int lastNode = 0;
        if (rightChild > size) { // 핵심
            return;
        }
        if (maxHeap[leftChild] > maxHeap[rightChild]) {
            lastNode = leftChild;
        } else {
            lastNode = rightChild;
        }
        if (maxHeap[i] >= maxHeap[lastNode]) {
            return;
        }
        swap(i, lastNode);
        heapify(lastNode);
    }

첫 데이터 제거 시 잘 되는 것 처럼 보였는데 다시보니 인덱스 감소랑 스왑이 안됨
완전 이진 트리이기 때문에 rightChild만 인덱스 체크 해주고 매번 새로운 루트가 되는
마지막 노드만 재귀를 통해 재정렬하면 된다.

util.PriorityQueue 사용

public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Random rand = new Random();
        for (int i = 0; i <= 10; i++) {
            pq.offer(rand.nextInt(20));
        }
        for (Integer i : pq) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.println(pq.poll());
        for (Integer i : pq) {
            System.out.print(i + " ");
        }
    }

Heap Sort 알고리즘 특징과 시간복잡도

• 완전 이진 트리(힙)의 특징을 따라가기 때문에 삽입과 삭제 연산의 속도는 $O(log N)$
  이진트리의 깊이에 따라서만 연산이 늘어나기 때문에 최악의 경우에도 트리의 깊이만큼 유지된다.
• 따라서 전체 요소 n개에 대한 힙 정렬의 시간 복잡도는 $O(N log N)$이 된다.
• 힙 정렬은 특정 최대, 최소값들을 뽑아낼 때 효율적이다.