본문 바로가기
알고리즘

이진 힙(binary heap)

브로리카 2023. 6. 14. 02:01

이진 힙이란?

완전 이진트리(Complete Binary Tree)의 한 형태로 힙 정렬, 또는 우선순위 큐에 사용된다.
이진 힙은 다음 2가지 특성을 가지고 있다.

  1. 완전 이진 트리와 동일하게 모든 레벨이 완전히 채워져 있다. 마지막 레벨은 왼쪽부터 순서대로 채워진다.
  2. 모든 부모 노드는 자식 노드보다 큰 값을 가진다. 이 경우, 최대 힙(Max Heap) 이라고 한다.
    반대로 부모 노드가 자식 노드보다 작은 값을 가지면 최소 힙(Min Heap)이라고 한다.

이 글에선 최소 힙을 기준으로 설명한다.

힙 선언

class Heap {
    private int[] heapArray;
    private int tail = 0;
    private int capacity;

    public Heap(int capacity) {
        this.heapArray = new int[capacity];
        this.capacity = capacity;
    }
	// 기타 메소드들 ...    
}

이진 힙은 노드로 관리하지 않고, 배열로 관리한다. 이유는 다음과 같다.

메모리 효율성

노드를 클래스 형태로 만들어 관리해야 하면, 각 노드에 대한 별도의 포인터를 가져야 한다.
인덱스만 계산해 접근하면 되는 배열과 달리 비효율적이다.

속도 효율성

객체를 생성, 해제 과정은 오버헤드가 발생한다.

접근 과정 역시 오버헤드가 발생하는데, 객체가 생성될 때는 힙의 빈 공간을 할당받는다.
객체를 연속으로 생성하는 것이 힙 내부에 연속적으로 할당된다는 보장이 없다.

 

즉, 캐시에서 공간 지역성이 떨어진다.
객체들이 하나의 디스크 블록에 담을 수 없을 정도로 간격이 떨어져 있다면 객체 하나를 가져올 때마다 캐시 미스와 메모리 폴트가 발생한다.


정리하면 객체가 10개 있다면 초기 상태에서 객체를 모두 가져오는데 10번의 I/O 작업이 발생하는 것이다.

인덱스 계산

부모 노드가 $i$이고, 루트 노드의 인덱스를 $0$이라 한다면
왼쪽 자식 노드는 $2 * i + 1 $이 되고, 오른쪽 자식 노드는 $2 * i + 2$ 이 된다.
자식에서 부모 노드로 가고 $(i - 1) / 2$ 을 한다.

 

어떤 글에서는 루트 노드 인덱스를 $1$로 하는 경우가 있는데
이 경우엔 왼쪽 자식 노드는 $2 * i$, 오른쪽 자식 노드는 $2 * i + 1$로 계산한다.
자식에서 부모 노드로 가고 싶다면 $i / 2$를 한다.

 

이 글에서는 루트 노드의 인덱스를 $0$으로 했다.

삽입

삽입은 다음 순서로 진행한다.

삽입 과정

  1. 이진트리의 마지막 레벨의 가장 왼쪽에 노드를 추가한다. (배열 내 마지막 원소 다음)
  2. 삽입된 노드와 부모 노드의 값을 비교한다.
  3. 최소 힙인 경우 값이 작을 때, 최대 힙인 경우 값이 클 때 값을 스왑 한다. 아니라면 재귀를 끝낸다.
  4. 부모 노드로 올라가 2번부터 시작한다.

$N$개의 원소를 삽입하면, $N$번의 조정작업이 발생하므로 시간 복잡도는 $O(NlogN)$이 발생한다.

    public void insert(int data) {
        // 한계에 도달하면 삽입 취소
        if (tail >= capacity) {
            return;
        }
        heapArray[tail] = data;
        int index = tail;
        tail += 1;
        upRecursive(getParentIndex(index), index);
    }

    private void upRecursive(int parent, int child) {
        // 자식이 루트 인덱스이거나, 자식이 부모보다 크면 return
        if (child <= 0 || heapArray[child] >= heapArray[parent]) {
            return;
        }
        swap(child, parent);
        upRecursive(getParentIndex(parent), parent);
    }

추출

추출은 우리가 사용하는 우선순위 큐의 pop 과 같은 원리다.

추출 과정

  1. 배열의 마지막원소를 배열의 $0$번 인덱스에 덮어쓴다. (반환을 할 경우 따로 저장해 놓는다.)
  2. 배열의 최대 인덱스를 $1$ 감소한다.
  3. 부모 인덱스(처음엔 루트)와 자식 노드의 값을 비교해 값이 작은 경우(최소 힙) 스왑 한다. 아니라면 재귀를 끝낸다.
  4. 자식 노드로 내려가 3부터 시작한다.

추출 작업 후 트리의 균형을 조절해야 하므로 $O(logN)$의 시간 복잡도가 발생한다.

    // 최솟값 추출
    public int extractMin() {
        int ret = getMin();
        heapArray[0] = heapArray[tail - 1];
        heapArray[tail - 1] = 0;
        tail -= 1;
        downRecursive(0);
        return ret;
    }

    private void downRecursive(int parent) {
        int child = parent;
        int leftIndex = getLeftChildIndex(parent);
        if (leftIndex < tail && heapArray[parent] > heapArray[leftIndex]) {
            child = leftIndex;
        }
        int rightIndex = getRightChildIndex(parent);
        if (rightIndex < tail && heapArray[child] > heapArray[rightIndex]) {
            child = rightIndex;
        }
        if (child != parent) {
            swap(parent, child);
            downRecursive(child);
        }
    }

정렬

이진트리이기 때문에 힙 정렬을 구현할 수 있다.
추출 과정과 비슷하지만 약간의 차이가 있다.
마지막 원소를 가리키는 인덱스를 $i$라고 할 때

  1. 배열의 첫 원소와 $i$의 위치를 바꾼다.
  2. $0$번 인덱스부터 시작해 부모 노드와 자식 노드의 값의 대소를 비교한다.
    단, 인덱스가 $i$ 이상이 되면 탐색을 중단한다.
  3. 배열의 마지막 인덱스$(tail - 1)$부터 $0$까지 1~2 과정을 반복

$N$개의 배열에 대해 $N$번 조정작업이 발생하므로 $O(logN)$의 시간 복잡도가 발생한다.

그림으로 표현하긴 너무 노가다여서.. 코드로 대체한다.

    public void descend() {
        System.out.print("내림차순 정렬: ");
        for (int i = tail - 1; i >= 0; i--) {
            int temp = heapArray[0];
            heapArray[0] = heapArray[i];
            heapArray[i] = temp;

            descendRecursive(0, i);
        }
        // 출력
        for (int i = 0; i < tail; i++) {
            System.out.printf("%d ", heapArray[i]);
        }
        System.out.println();
    }

    private void descendRecursive(int parent, int limit) {
        int child = parent;
        int leftIndex = getLeftChildIndex(parent);
        if (leftIndex < limit && heapArray[parent] > heapArray[leftIndex]) {
            child = leftIndex;
        }
        int rightIndex = getRightChildIndex(parent);
        if (rightIndex < limit && heapArray[child] > heapArray[rightIndex]) {
            child = rightIndex;
        }
        if (child != parent) {
            swap(parent, child);
            descendRecursive(child, limit);
        }
    }

키 변경

상황에 따라선 힙에 있는 값을 바꿀 상황이 있다.
이 경우, 해당 인덱스가 가리키는 값을 바꾼 뒤
삽입 과정과 동일하게 부모 노드와 자식 노드 간 대소 비교를 수행한다.

추출작업과 동일하게 $O(logN)$의 시간 복잡도가 발생한다.

    public void updateKey(int key, int newValue) {
        if (key >= tail) {
            return;
        }
        heapArray[key] = newValue;
        upRecursive(getParentIndex(key), key);
    }
    
    // upRecursive 코드 생략

 

전체 코드는 아래에서 볼 수 있다.

더보기 
public class HeapTree {

    private static Heap heap = new Heap(256);

    public static void main(String[] args) {
        heap.insert(5);
        heap.insert(1);
        heap.insert(2);
        heap.insert(4);
        heap.insert(3);
        heap.insert(6);
        heap.insert(10);
        heap.insert(9);
        heap.insert(8);
        heap.insert(7);
        // descend와 priorityPrint는 따로 실행해야 한다.
        heap.descend();
//        heap.priorityPrint();
    }
}

class Heap {
    private int[] heapArray;
    private int tail = 0;
    private int capacity;

    public Heap(int capacity) {
        this.heapArray = new int[capacity];
        this.capacity = capacity;
    }

    public void insert(int data) {
        // 한계에 도달하면 삽입 취소
        if (tail >= capacity) {
            return;
        }
        heapArray[tail] = data;
        int index = tail;
        tail += 1;
        upRecursive(getParentIndex(index), index);
    }

    private void upRecursive(int parent, int child) {
        // 자식이 루트 인덱스이거나, 자식이 부모보다 크면 return
        if (child <= 0 || heapArray[child] >= heapArray[parent]) {
            return;
        }
        swap(child, parent);
        upRecursive(getParentIndex(parent), parent);
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private void swap(int childIndex, int parentIndex) {
        int temp = heapArray[parentIndex];
        heapArray[parentIndex] = heapArray[childIndex];
        heapArray[childIndex] = temp;
    }

    public int getMin() {
        return heapArray[0];
    }

    public int extractMin() {
        int ret = getMin();
        heapArray[0] = heapArray[tail - 1];
        heapArray[tail - 1] = 0;
        tail -= 1;
        downRecursive(0);
        return ret;
    }

    private void downRecursive(int parent) {
        int child = parent;
        int leftIndex = getLeftChildIndex(parent);
        if (leftIndex < tail && heapArray[parent] > heapArray[leftIndex]) {
            child = leftIndex;
        }
        int rightIndex = getRightChildIndex(parent);
        if (rightIndex < tail && heapArray[child] > heapArray[rightIndex]) {
            child = rightIndex;
        }
        if (child != parent) {
            swap(parent, child);
            downRecursive(child);
        }
    }

    public void updateKey(int key, int newValue) {
        if (key >= tail) {
            return;
        }
        heapArray[key] = newValue;
        upRecursive(getParentIndex(key), key);
    }

    public void descend() {
        System.out.print("내림차순 정렬: ");
        for (int i = tail - 1; i >= 0; i--) {
            int temp = heapArray[0];
            heapArray[0] = heapArray[i];
            heapArray[i] = temp;

            descendRecursive(0, i);
        }
        // 출력
        for (int i = 0; i < tail; i++) {
            System.out.printf("%d ", heapArray[i]);
        }
        System.out.println();
    }

    private void descendRecursive(int parent, int limit) {
        int child = parent;
        int leftIndex = getLeftChildIndex(parent);
        if (leftIndex < limit && heapArray[parent] > heapArray[leftIndex]) {
            child = leftIndex;
        }
        int rightIndex = getRightChildIndex(parent);
        if (rightIndex < limit && heapArray[child] > heapArray[rightIndex]) {
            child = rightIndex;
        }
        if (child != parent) {
            swap(parent, child);
            descendRecursive(child, limit);
        }
    }

    public void priorityPrint() {
        System.out.print("오름차순 우선순위 큐: ");
        int N = tail;
        for (int i = 0; i < N; i++) {
            System.out.printf("%d ", extractMin());
        }
        System.out.println();
    }
}

 

https://github.com/brorica/DataStructure/blob/master/src/HeapTree.java

 

GitHub - brorica/DataStructure: 수상할 정도로 나무를 좋아하는 레포

수상할 정도로 나무를 좋아하는 레포. Contribute to brorica/DataStructure development by creating an account on GitHub.

github.com

 

'알고리즘' 카테고리의 다른 글

레드 블랙 트리(red black tree)  (0) 2023.06.25
AVL 트리 (Adelson-Velsky and Landis Tree)  (0) 2023.06.11
이진 탐색 트리 (Binary Search Tree)  (0) 2023.06.10
트리, 이진트리  (1) 2023.06.09
2022 KAUPC 2회 출제 후기  (0) 2022.09.18

'알고리즘' Related Articles

티스토리툴바