dev 기타 (Etc)

자료구조 힙 (Data structure heap)

2020.02.13 ·

자료구조 힙은 무엇이고 어떻게 구현하는가?

목차

어떤 회사 기술면접 때, 질문 받았던 것 중에 힙(heap)이 있었습니다.

1. 힙은 언제 쓰면 좋은가?
2. 힙을 구현할 때 사용하면 좋은 자료구조는 무엇인가?
3. 힙의 탐색에 걸리는 시간복잡도는 무엇인가?

제 대답은

1. 인풋 값이 있을 때, min, max 값을 뽑아낼 때, 사용하면 좋을 것이라 생각합니다.
2. 힙을 구현하기 간편한 자료구조는 배열이라고 생각합니다.
3. 만약 최대 힙에서 최소 값을 찾는다고 가정하면 O(n)이라고 생각합니다.

이었습니다.

그럼 바로 힙에 대해서 설명하면 다음과 같습니다.

최대힙의 경우, 완전 트리이면서 root가 모든 경우에 자식들보다 커야 한다.
최소힙의 경우, 완전 트리이면서 root가 모든 경우에 자식들보다 작아야 한다.

완전트리는 다음과 같은 규칙을 지키는 바이너리 트리(binary tree) 입니다.

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.

public class MyHeap {
    private int[] data;
    private int size;
    private int maximumSize;

    public MyHeap() {
        data = new int[100];size = 0;
    }

    public MyHeap (int maximumSize) {
        this.maximumSize = (maximumSize < 1) ? 100 : maximumSize;
        data = new int[this.maximumSize];size = 0;
    }

    public boolean isEmpty() {
        return (this.size == 0);
    }

    public boolean isFull() {
        return (this.size == this.maximumSize);
    }

    public void clear() {
        data = null;
    }

    public void insert(int num) {
        int pointer;
        if (isFull()) {
            throw new ArrayIndexOutOfBoundsException();
        }else {
            data[size] = num;
            pointer = size++;

            while (pointer > 0 && data[pointer] > data[(pointer - 1) / 2]) {
                int tmp = data[pointer];
                data[pointer] = data[(pointer - 1) / 2];
                data[(pointer - 1) / 2] = tmp;
                pointer = (pointer - 1) / 2;
            }
        }
    }

    public int delete() {
        int t;
        if (isEmpty()) {
            throw new ArrayIndexOutOfBoundsException();
        }else {
            t = data[0];
            data[0] = data[--size];
            data[size] = 0;
            reHeap();
            return t;
        }
    }

    public void reHeap() {
        int pointer = 0;
        while (pointer * 2 + 1 < size) {
            if (data[pointer * 2 + 1] > data[pointer * 2 + 2]) {
                int t = data[pointer];
                data[pointer] = data[pointer * 2 + 1];
                data[pointer * 2 + 1] = t;
                pointer = pointer * 2 + 1;
            }else {
                int t = data[pointer];
                data[pointer] = data[pointer * 2 + 2];
                data[pointer * 2 + 2] = t;
                pointer = pointer * 2 + 2;
            }
        }
    }


    public int[] sort() {
        int[] sort = new int[this.size];
        for (int i = 0; i < sort.length; i++) {
            sort[i] = this.delete();
        }
        return sort;
    }


    public static void main(String[] args) {
        MyHeap heap = new MyHeap(100);
        heap.insert(5);
        heap.insert(3);
        heap.insert(7);
        heap.insert(4);
        heap.insert(2);
        heap.insert(6);
        heap.insert(1);
        int[] arr = heap.sort();
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }

}

힙의 heapify 관련한 시뮬레이션

면접 질문에 대한 정확한 대답은 무엇일까요?

1. 힙은 언제 쓰면 좋은가? - 전체 시퀀스가 아닌 부분 시퀀스도 정렬이 되어있어야할 때 사용하면 좋다. (전체 n 개중 m개만 인풋이 들어온 상태)
2. 힙을 구현할 때 사용하면 좋은 자료구조는 무엇인가? (구현의 편의성을 위해서는 배열(자신의 자식노는 m * 2, m * 2 + 1 이므로 찾기 쉬움), 보통은 트리 형태로 구현)
3. 힙의 탐색에 걸리는 시간복잡도는 무엇인가? O(n)

   Space		O(n)	O(n)
   Search		O(n)	O(n)
   Insert		O(1)    O(n)
   Delete		O(log n) O(log n)
   Peek	        O(1)   O(1)