Heap 의 특성을 살펴보고 Heap sort 를 구현해보자.

2019-10-21 1ilsangData-Structure & Algorithm

힙은 최댓값/최소값을 빠르게 찾아내기 위해 고안된 ‘완전이진트리’ 자료구조이다.

여기서 중요한 점은 최대/최소의 값을 ‘검색’하는데 O(1) 의 시간복잡도를 가진다는 점이다. 이때 값을 얻기 위해 pop을 하게 되면 O(logN)의 시간이 걸린다. 또한 맨 처음 펼쳐진 N개의 값들을 힙에 세팅해 주어야 하므로 N 의 시간이 더 걸리게 된다. 그렇기 때문에 힙의 시간복잡도는 O(NlogN)이라고 이야기 한다.

요약하자면 힙 트리 세팅을 하기위해 N 개의 원소를 다 넣어야하므로 N 의 시간이 걸리고, 이때마다 노드가 이진트리를 타게되므로 절반씩 값들을 걸러 움직여(logN 의 시간) 총 NlogN 의 시간이 걸리게 된다.

즉 굉장히 빠르고 효율적인 자료구조이다.

힙을 이용하는 경우는 무궁무진한데, 양수 가중치 최단거리를 구하는 다익스트라 알고리즘을 구현할 때 우선순위큐를 사용하면 훨씬 효율적으로 다음 노드를 찾아갈 수 있게 된다. 여기서 잠깐! 갑자기 웬 우선순위큐? 우선순위큐는 Heap 으로 구현되어 있다!

위의 내용을 토대로 힙의 특성을 정리하면 아래와 같다.

완전이진트리이다.
자식은 반드시 부모보다 크거나 작다(최대/최소 힙)
PriorityQueue 는 Heap 으로 구성되어 있다.
O(NlogN) 의 시간복잡도를 가진다.

힙을 구현하기 이전에 push, pop 연산에서 노드가 어떻게 움직이는지 미리 알아두고 가자.

Push

트리의 마지막 노드에 값을 넣는다.
부모 노드와 값을 비교한다.
루트에 도달하거나, 부모 노드보다 값이 작다면(최대힙기준) break 한다.
부모 노드보다 값이 크다면 부모 노드와 swap 한다.
재귀적으로 다시 부모 노드와 비교한다.(2번부터 다시 시작)

Pop

트리의 루트값을 저장한다.(return 용)
트리의 마지막 노드를 루트로 올린다.
왼쪽 자식노드, 오른쪽 자식노드, 자신 3개의 값을 비교한다.
자신이 가장 크다면(최대힙기준) break 한다.
아니라면 가장 큰 값과 swap 한다.
재귀적으로 다시 왼쪽, 오른쪽 자식노드와 비교한다.(3번부터 다시 시작)

구현은 위의 로직을 그대로 코드로 옮기면 된다.

public class MyHeap {
    private int[] arr;
    private int idx;

    MyHeap(int size) {
        idx = 0;
        arr = new int[size + 1];
    }

    public boolean push(int value) {
        if(idx + 1 >= arr.length) return false;

        arr[++idx] = value;

        int curIdx = idx;
        while(curIdx > 1) {
            int parentIdx = curIdx >> 1;
            if(arr[parentIdx] >= arr[curIdx]) break;

            int tmp = arr[parentIdx];
            arr[parentIdx] = arr[curIdx];
            arr[curIdx] = tmp;
            curIdx >>= 1;
        }

        return true;
    }

    public int pop() {
        if(idx < 1) return -1;
        int ret = arr[1];
        int curIdx = 1;

        arr[1] = arr[idx];
        arr[idx--] = 0;

        while(curIdx <= idx) {
            int tmpIdx = curIdx;
            if(curIdx * 2 <= idx && arr[tmpIdx] < arr[curIdx * 2]) tmpIdx = curIdx * 2;
            if(curIdx * 2 + 1 <= idx && arr[tmpIdx] < arr[curIdx * 2 + 1]) tmpIdx = curIdx * 2 + 1;
            if(curIdx == tmpIdx) break;

            int tmp = arr[tmpIdx];
            arr[tmpIdx] = arr[curIdx];
            arr[curIdx] = tmp;
            curIdx = tmpIdx;
        }

        return ret;
    }
}

위에서 정리한 push/pop flow 에 따라 그대로 구현한 코드이다. 천천히 따라가면서 읽으면 큰 무리 없을 것이라 본다.

그럼 이제 힙소트를 구현해보자.

class Main {
    public static void main(String[] args) {
        MyHeap heap = new MyHeap(10);
        int[] list = {1, 2, 3, 4, 5, 6, 7, 8};

        for (int i = 0; i < list.length; i++) {
            heap.push(list[i]);
        }

        for (int i = 0; i < list.length; i++) {
            System.out.printf(heap.pop() + " ");
        } // 8 7 6 5 4 3 2 1
    }
}

힙을 구현하면 힙 소트는 push/pop 연산으로 자연스럽게 가능한 것을 볼 수 있다.

이상으로 힙을 마무리 하려고 한다. 다음에는 문자열 알고리즘으로 돌아와야지!!

그럼 이만!