[알고리즘] [1] 힙 정렬

1. 힙

우선순위 큐(Priority Queue)를 위하여 만들어진 자료구조로, 완전이진트리를 사용하므로 빈 요소가 없어 배열로 구현한다.

2. 힙 정렬

힙 정렬이란 최대 힙 트리 또는 최소 힙 트리를 구성하여 정렬하는 방식이다.

 최소 힙 알고리즘 

1. n개의 노드에 대한 완전이진트리를 구성한다. Parent, LeftChild, RightChild로 구성된다. 완전이진트리이기 때문에 어떤 한 노드에 대한 Parent, LeftChild, RightChild의 Index를 구할 수 있다. 

2. 부모 노드가 자식 노드보다 작은 최소 힙을 구성한다.

3. 루트 노드와 가장 아래의 노드와 교환하고, 교환된 가장 아래의 노드를 제외한 나머지에 대해 최소 힙을 구성한다.

4. 2와 3을 반복하여 오름차순으로 정렬한다.

package B;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        minHeap heap = new minHeap(n); // pack, ans 생성
        for (int i = 0; i < n; i++) {
            heap.add(sc.nextInt()); // add()로 upHeap 규칙에 맞추어 정렬
        }
        for (int i = 0; i < n; i++) {
            heap.delete(i); // 가장 상위 노드부터 ans에 담고 downHeap() 적용
            System.out.print(heap.ans[i] + " ");
        }
    }
}
class minHeap {
    static int size = 0; // pack은 길이가 n으로 유지되기 때문에, 현재 작업 상 마지막 노드의 위치를 확인하기 위한 변수
    int [] pack; // 수를 하나씩 담고 add()를 통해서 한 턴마다 노드를 계속 바꿔줌
    int [] ans; // pack에서 맨 위의 노드를 담는 배열
    public minHeap (int n) {
        pack = new int [n];
        ans = new int [n];
    }
    public void add (int i) {
        pack[size] = i; // 마지막 노드에 값 저장
        upHeap(size); // 마지막 노드가 부모 노드보다 작다면 swap
        size++; // 다음 작업을 위해 마지막 노드 index 수정
    }
    public void upHeap (int size) {
        int p = getParentIndex(size);
        int c = size;
        while (pack[p] > pack[c] && p >= 0) { // 부모 노드가 더 크다면
            swap (p, c); // 위치를 변경한다
            c = p; // 다음 부모와 자식 재정의 후 조건을 만족하는 동안 반복
            p = getParentIndex(c);
        }
    }
    public void swap (int a, int b) { // 위치 변경 함수
        int save = pack[a];
        pack [a] = pack [b];
        pack [b] = save;
    }
    public int getLeftChildIndex (int i) {
        return i * 2 + 1;
    }
    public int getRightChildIndex (int i) {
        return i * 2 + 2;
    }
    public int getParentIndex (int i) {
        return (i - 1) / 2;
    }
    public void delete (int i) {
        size--;
        ans[i] = pack[0];
        swap(0, size); // 가장 상위 노드와 가장 아래 노드를 교환한다.
        downHeap();
    }
    public int getMinChildIndex (int i) {
        int l = getLeftChildIndex(i);
        int r = getRightChildIndex(i);
        if (l < size && r < size) {
            if (pack[l] > pack[r]) return r;
            else return l;
        } else if (l < size) {
            return l;
        } else return -1;
    } // 자식 노드 중 더 작은 값을 가진 자식을 찾는다. 만약 자식이 없다면 -1을 return하고 이후 downHeap()에서 -1인 경우 break하는 방식
    public void downHeap () {
        int i = 0;
        while (i < size) { // i는 계속 더 작은 값을 가지는 자식 노드 index로 업데이트
            int min = getMinChildIndex(i); // 자식 노드 중 더 작은 값의 index 저장
            if (min == -1) break; // 자식 노드가 없다면 종료
            if (pack[i] > pack[min]) {
                swap(i, min); // 더 작은 값과 swap
                i = min;
            } else break; // 더 작은 자식 노드가 없다면 종료
        }
    }
}