힙(Heap)의 2가지 코딩(루프 vs 리커전)

알고리즘에서 힙(Heap) 이란? 바이너리 트리를 사용해서, 부모노드의 값이, 2개의 자식노드 보다 항상 크도록 유지하는 것이 힙 입니다. 따라서, 루트노드는 항상 전체 트리에서 가장 큰 값을 가지게 됩니다.
(반대로 부모노드값이 자식노드 보다 항상 작게 유지하는 것도 가능하지만, 여기서는 크도록 유지하는 힙만 다루겠습니다.)

이런 힙의 성질을 활용하여 정렬하는 방식을 Heap Sort라고 하고, $$ O(N \cdot {log_2 N}) $$ 시간복잡도로 정렬이 가능한 정렬방식입니다. 여기서는 힙의 2가지 코딩방식(루프/리커전)에 대해서 알아 보겠습니다.

자바 소스 코드 : https://github.com/skysign/WSAPT/blob/master/Heap%20sort/src/com/tistory/skysign/Heap_sort/HeapSort.java

2가지 방식으로 힙을 구현할 수 있구요, 각각 아래 링크에서 참고했습니다.

• 힙 루프 코딩 / 알고리즘문제해결전략 2권 페이지 728~730 https://book.algospot.com
• 리커전 코딩 / https://www.geeksforgeeks.org/java-program-for-heap-sort

힙 루프 코딩

책 2권 코드 23.1, 23.2 에서 힙에 아이템 하나를 넣고 빼는 코드에 대해서 C++ STL을 사용하여 코딩되어 있구요, 여기서는 자바로 코딩을 설명드리겠습니다.

v 가 새로 추가할 아이템고, al 이 vector 대신에 사용하는 ArrayList container입니다.

힙에 아이템 추가하기

아이템을 al의 제일 마지막에 추가하고, 아래순서를 제일 첫번째 index 0번까지 반복합니다.

• al의 끝에 아이템 추가, index는 마지막 아이템의 index
• 추가한 아이템의 parent와 비교 하고 작으면 swap
• parent of parent와 parent위치를 비교하기 위해서, index 에 parent index를 저장

    /*
     * heap을 ArrayList를 사용해서, 루프를 이용해서 구현하는 방법입니다.
     */
    public void push_heap(ArrayList<Integer> al, int v) {
        // 새로운 v 를 마지막에 추가합니다.
        al.add(v);

        // idx는 새로 추가한 v의 위치 입니다.
        int idx = al.size() - 1;

        // (idx - 1) / 2 는 idx의 parent index입니다.
        // idx(즉 child)와 parent index의 값을 서로 비교해서,
        // parent 의 값이 작으면 서로 swap합니다.
        while(  (idx > 0) &&
                al.get((idx - 1) / 2) < al.get(idx)) {
            // swap 하고
            Collections.swap(al, (idx - 1) / 2, idx);

            // parent 와 parent of parent를 비교하기 위해서,
            // idx에 parent index를 저장합니다.
            idx = (idx - 1) / 2;
        }
    }

힙에 아이템 꺼내기

• al의 가장 첫번째 0번을 꺼냄
• 마지막과 0번을 swap
• 마지막을 삭제

1. 0번이 힙트리에서 올바른 위치를 찾아가기 위한 여정의 시작
2. 왼쪽과 비교하고
3. 오른쪽과 비교하고
4. 왼쪽/오른쪽 중에서 큰쪽과 idx 를 swap
5. 1~4번을 반복함

    public int pop_heap(ArrayList<Integer> al) {
        int r = al.get(0);

        Collections.swap(al, 0, al.size()-1);
        al.remove(al.size() - 1);

        int idx = 0;

        while(true) {
            int idxL = (idx<<1) +1;
            int idxR = (idx<<1) +2;
            int idxSwap = idx;

            if(idxL >= al.size())
                break;

            if(al.get(idxSwap) < al.get(idxL))
                idxSwap = idxL;
            if((al.size() > idxR) && (al.get(idxSwap) < al.get(idxR)))
                idxSwap = idxR;

            if(idx == idxSwap)
                break;

            Collections.swap(al, idxSwap, idx);
            idx = idxSwap;
        }

        return r;
    }

힙 리커전 코딩

동작 방식은 위의 루프코딩과 동일하지만, 코딩을 리커전으로 했다는 것만 다릅니다.
정렬이 되어있지 않은 배열 d 를 heapSort 메서드에서 정렬합니다.

heapify() 메서드는 heap 상태가 아닌 배열을 heap 상태로 만들어 주는 메서드입니다.

    public void heapSort(int d[]) {
        // build max heap
        // 즉, binary tree로 child가 항상 parent 보다 작은 상태를 만들겠습니다.

        // N : 트리에 있는 노드의 숫자
        int N = d.length;

        // N>>1 해서 N을 2로 나누고 -1 한 인덱스 부터, root node은 0까지 heapify 합니다.
        // N/2-1 ~ 0 까지 루프를 한다는 것은, 바이너리 트리에서 sibling 을 제외 하고,
        // 나머지 노드 들에 대해서, 모두 방문해서 heapify 한다는 것입니다.
        // heapify는 child가 parent보다 작은 상태가 되도록, child와 parent를 swap하는 일을 말합니다.
        for(int i= (N>>1) -1; i>=0; --i) {
            heapify(d, N, i);
        }
        // N/2-1 ~ 0 까지 heapify가 끝나면, index 0 에 가장 큰 값이 위치 하게 됩니다.

        for(int i=N-1; i>=0; --i) {
            // index 0에 가장 큰 값이 있으므로, index 0 번과 마지막 index를 swap 합니다.
            int t = d[0];
            d[0] = d[i];
            d[i] = t;
            // 가장 큰 값이, 이제 제일 끝에 위치하게 되었습니다.

            // 가장 큰 값을 찾았으니, 이제 tree의 크기를 1 줄여서
            // 그 다음 큰 값을 찾기위해서, heapify 할 차례입니다.
            heapify(d, i, 0);
        }
    }

    public void heapify(int[] d, int N, int idxParent) {
        // 가장 큰 값을 가지고 있는 인덱스가 i 라고 가정하고,
        // 이후에 idxBiggest가 i 값과 다르면, 아래의 2가지 스텝을 실행 합니다.
        int idxBiggest = idxParent;
        int idxLeftChild = (idxParent<<1) +1;
        int idxRightChild = (idxParent<<1) +2;

        // binary tree이지만, full binary tree가 아닐 수 있기 때문에,
        // idxLeftChild와 idxRightChild모두 N 보다 작을 때만, 비교 해야 합니다.
        if((idxLeftChild < N) && d[idxLeftChild] > d[idxBiggest])
            idxBiggest = idxLeftChild;

        if((idxRightChild < N) && d[idxRightChild] > d[idxBiggest])
            idxBiggest = idxRightChild;

        if(idxBiggest != idxParent) {
            // idxBiggest와 idxParent 값을 swap 합니다.
            int t = d[idxParent];
            d[idxParent] = d[idxBiggest];
            d[idxBiggest] = t;

            // idxBiggest에 idxParent값이 들어 왔으므로,
            // idxBiggest에 대해서, heapify합니다.
            heapify(d, N, idxBiggest);
        }
    }