자료구조 힙(Heap)

완전 이진 트리의 일종으로 우선 순위 큐를 위해 만들어진 구조
최대 값, 최소 값을 쉽게 추출할 수 있다.

	   7
	 /  |
	5   6 
  / |  / |
 1  2  3  4

이런 모습 (완전 이진 트리)

• 최대 힙 트리나, 최소 힙 트리를 사용하여 정렬
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 과정 설명
  - 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
  내림차순을 기준으로 정렬
  - 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
  - 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

내림차순 정렬을 위한 최대 힙(max heap)의 구현

힙(heap)은 1차원 배열로 쉽게 구현될 수 있다.
정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다.
최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

최대 힙(max heap)의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

구현 (Java)

    public static void heapify(int[] lst, int n, int i) {
        int largest = i;         // 현재 노드
        int left = 2 * i + 1;    // 왼쪽 자식
        int right = 2 * i + 2;   // 오른쪽 자식

        // 왼쪽 자식이 더 크면 largest 갱신
        if (left < n && lst[left] > lst[largest]) {
            largest = left;
        }

        // 오른쪽 자식이 더 크면 largest 갱신
        if (right < n && lst[right] > lst[largest]) {
            largest = right;
        }

        // largest가 변경되었으면 교환 및 재귀적으로 힙화
        if (largest != i) {
            int temp = lst[i];
            lst[i] = lst[largest];
            lst[largest] = temp;

            // 재귀적으로 하위 트리를 힙화
            heapify(lst, n, largest);
        }
    }

    public static void heapSort(int[] lst) {
        int n = lst.length;

        // 힙 빌드: 최대 힙 생성
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(lst, n, i);
        }

        // 힙 정렬
        for (int i = n - 1; i > 0; i--) {
            // 루트(가장 큰 값)를 끝으로 보냄
            int temp = lst[0];
            lst[0] = lst[i];
            lst[i] = temp;

            // 나머지 힙화
            heapify(lst, i, 0);
        }
    }