자바[JAVA] 자료구조 구현 7 - Heap

0. 들어가기 전

 

Heap은 '우선순위 큐'에 사용되기 위해 필수적으로 알아야 하는 자료구조입니다. 추가적으로 흔히 동적으로 변수를 만들 때 해당 변수가 저장되는 공간인 Heap 과는 다른 의미입니다.

 

1. Heap

 

Heap 은 최소값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조입니다. 이진 트리는 아는데 완전 이진트리는 무엇일까?

 

1.1 Complete Binary Tree

 

트리(Tree)는 계층 구조를 갖는 자료구조로서, 서로 연결되어 있는 노드들의 집합입니다. 트리에는 자식들과 가지의 형태로 연결되어있는 루트 노드가 있습니다. 이때 이진 트리(Binary Tree)는 자식 노드의 개수를 최대 2개로 정한 트리입니다. 

 

사실 이진 트리는 우리가 일전에 살펴본적이 있습니다. BST 나 AVL 은 이진 트리를 이용한 자료구조입니다.

2024.04.20 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 8 - Binary Search Tree

자료구조 및 알고리즘 8 - Binary Search Tree

2024.05.02 - [자료구조 및 알고리즘] - 자료 구조 및 알고리즘 9 - AVL Tree

자료 구조 및 알고리즘 9 - AVL Tree

 

그렇다면 완전 이진트리(Complete Binary Tree)는 무엇일까요?

이진 트리에는 다양한 종류가 있습니다. 이는 한국어로 번역되면서 오해를 불러일으킬 수 있기 때문에 영어로 적어보겠습니다.

• Full Binary Tree: 모든 노드들은 0개 혹은 2개의 자식 노드만을 갖습니다.
• Complete Binary Tree: 마지막 레벨을 제외한 모든 레벨에서 노드들이 가득 차 있습니다. 그리고 마지막 레벨의 노드들은 왼쪽에서부터 차 있습니다.
• Perfect Binary Tree: 모든 노드들은 오직 2개의 자식 노드만을 갖습니다. 모든 잎 노드들은 같은 레벨에 존재합니다.

Heap 은 Complete Binary Tree 를 기반으로 구현됩니다.

 

1.2 Properties of Heap

 

heap 자료구조는 최대 최소값을 빠르게 찾기 위해서 고안된 자료구조입니다. Complete Binary Tree 를 통해 어떻게 이를 수행할 수 있을까요?

 

일반적인 Binary Tree 에 값들을 저장하고 최소값을 찾는다면 아마 O(logN) 이 소요될 것입니다. 이보다 빠르게 최소값을 찾는 방법은 아마 O(logN) 보다 빠른 O(N) 정도일 것 같습니다. 하지만 O(logN) 보다 빠르게 무언가를 찾는 방법은 별로 없을 것 같습니다.

 

같은 O notation 이지만 그 안에서 더 빠른 방법을 찾기 위해서 컴퓨터 과학자들은 Complete Binary Tree 에 특정한 Rule 을 부여하는 자료구조인 Heap 을 만들었습니다.

 

부모 노드는 항상 자식 노드보다 우선순위가 높다

 

이때 우선순위란 쉽게 설명하기 위해 노드의 key 값이라고 가정합니다. 그리고 key 값이 작으면 우선순위가 높다고 가정합니다.

 

heap

 

해당 규칙을 통해서 우리는 루트노드가 가장 우선순위가 높다는 사실을 알 수 있습니다. 우선순위 2등, 3등, 4등 ... 의 위치는 불완전하게 찾을 수밖에 없지만 우리가 관심이 있는건 오직 최우선순위이기 때문에 별로 중요하지 않습니다.

 

그리고 2등, 3등, 4등... 의 위치가 비교적 자유롭기 때문에 이는 많은 variation 이 존재한다는 의미이고, 이는 수행시간을 줄여줍니다.(* 강한 규칙이 없다는 것은 하나하나 노드의 위치를 정해줄 필요가 없다는 의미)

 

1.3 Index array

 

위에 트리를 구현하기 위한 방법은 많습니다. 이전에 저희가 했던 방식처럼 LinkedList 의 형식을 따를 수도 있지만 일반적으로 Heap 은 배열을 통해서 구현합니다.

 

각 노드의 위치를 index 로 나타내고 그 index 자리에 각 노드의 key 값을 저장해줍니다.(* 해당 방식 때문에 노드의 빈자리가 많아지게 된다면 배열에 빈 공간이 많이 생기고 저장공간의 비효율이 level 이 늘어남에 따라 기하 급수적으로 커집니다.) 

해당 배열의 특징으로

• 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
• 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
• 부모 노드 인덱스 = 자식 노드 인덱스 / 2

가 있습니다.

 

2. Heap 구현

 

2.1 Heap 생성자 및 기본 함수

import java.util.Comparator;

public class Heap<E> {
    
    private final Comparator<? super E> comparator;
    private static final int DEFAULT_CAPACITY = 10; // 기본 용적량
    private int size; // 요소 개수
    private Object[] array; // 요소를 담을 배열
    
    // 초기 사이즈 결정 x && comparator 가 필요 없는 경우
    public Heap(){
        this(null);
    }
    
    // 초기 사이즈 결정 x && comparator 가 필요한 경우
    public Heap(Comparator<? super E> comparator){
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.comparator = comparator;
    }
    
    // 초기 사이즈 결정 && comparator 가 필요 없는 경우
    public Heap(int capacity){
        this(capacity, null);
    }
    
    // 초기 사이즈 결정 && comparator 가 필요한 경우
    public Heap(int capacity, Comparator<? super E> comparator){
        this.array = new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }
    
    // 해당 인덱스의 부모 노드 인덱스 반환
    private int getParent(int index){
        return index / 2;
    }
    
    // 해당 인덱스의 왼쪽 자식 노드 인덱스 반환
    private int getLeftChild(int index){
        return index * 2;
    }
    
    // 해당 인덱스의 오른쪽 자식 노드 인덱스 반환
    private int getRightChild(int index){
        return index * 2 + 1;
    }
}

 

2.2 resize() and add() 함수

comparator 가 있는 경우와 없는 경우를 나눠서 생각했습니다. comparator 가 있는 경우는 해당 comparator 의 compare 함수를 사용하면 되지만, comparator 가 없고, comparable 을 E 가 상속한 경우라면, E.compareTo() 를 사용해야 합니다.

 

하지만 E.compareTo() 는 불가능하기에 E 타입 객체인 value 를 Comparable 타입으로 타입 캐스팅, 그리고 compareTo 를 사용해줍니다.

 

ShiftUp 의 경우, 부모 노드와 우선 순위를 비교, 우선 순위가 자식 노드가 높으면 위로 올라가는 방식입니다.

shift-up

/**
     * @param newCapacity 새로운 용적 크기
     */
    // parameter 로 입력되는 크기 만큼 재할당
    private void resize(int newCapacity){

        // 새로 만들 배열
        Object[] newArray = new Object[newCapacity];

        // 새 배열에 기존에 있던 배열의 요소들을 모두 복사해준다
        newArray = Arrays.copyOf(array, size);

        this.array = null;
        this.array = newArray;
    }

    public void add(E value){

        // 배열 용적이 꽉 차있을 경우 용적을 두 배로 늘려준다
        if(size + 1 == array.length){
            resize(array.length * 2);
        }

        shiftUp(size + 1, value); // value 가 추가되는 위치와 값을 넘겨줌
        size++; // 크기 증가
    }

    private void shiftUp(int idx, E value) {

        array[idx] = value;
        // comparator 가 있는 경우 comparator 를 넘겨줌
        if(comparator != null)
            shiftUpComparator(idx, value, comparator);
        else{
            shiftUpComparable(idx, value);
        }
    }

    @SuppressWarnings("unchecked")
    private void shiftUpComparable(int idx, E value) {

        // Comparable 구현체가 있어야 compareTo 를 쓸 수 있다.
        Comparable<? super E> comp = (Comparable<? super E>) value;

        // root 노드까지만 진행
        while(idx > 1){
            int parentIdx = getParent(idx);

            // 타겟 노드의 값이 부모 노드 값보다 크면 위로 올라갈 수 없음
            if(comp.compareTo((E)array[parentIdx]) >= 0)
                break;

            // swap
            E temp = (E) array[parentIdx];
            array[parentIdx] = array[idx];
            array[idx] = temp;

            // heap up
            idx = parentIdx;
        }
    }

    @SuppressWarnings("unchecked")
    private void shiftUpComparator(int idx, E value, Comparator<? super E> comparator) {

        // root 노드까지만 진행
        while(idx > 1){
            int parentIdx = getParent(idx);

            // 타겟 노드의 값이 부모 노드 값보다 크면 위로 올라갈 수 없음
            if(comparator.compare(value, (E) array[parentIdx]) >= 0)
                break;

            // swap
            E temp = (E) array[parentIdx];
            array[parentIdx] = array[idx];
            array[idx] = temp;

            // heap up
            idx = parentIdx;
        }
    }

 

2.3 remove()

삭제의 경우 케이스를 "비어있는 경우", "하나만 남아있었던 경우" 그리고 "여러 개가 있었던 경우" 로 나누어서 생각해야합니다. 그리고 크기가 줄었을 때 그 크기에 맞게 용적을 재할당해주는 기능 또한 필요합니다.

    @SuppressWarnings("unchecked")
    public E remove(){

        // 비어있는 경우
        if(array[1] == null){
            throw new NoSuchElementException();
        }

        // 최우선 노드
        E priorValue = peek();

        // 요소가 하나밖에 없는 경우
        if(size == 1) {
            array[1] = null;
            size--;
            return  priorValue;
        }

        shiftDown((E) array[size]);

        // 마지막 노드 삭제
        array[size] = null;
        size--;

        // 용적 재할당
        if(size + 1 <= DEFAULT_CAPACITY || size + 1 < array.length / 4)
            resize(Math.max(DEFAULT_CAPACITY, array.length / 2));

        return priorValue;
    }

    private void shiftDown(E value) {

        array[1] = value;
        if(comparator != null)
            shiftDownComparator(value, comparator);
        else
            shiftDownComparable(value);
    }

    @SuppressWarnings("unchecked")
    private void shiftDownComparable(E value) {

        // 루트 노드부터 시작
        int idx = 1;

        Comparable<? super E> comp = (Comparable<? super E>) value;

        // 자식 index 가 범위를 넘어가면 종료, 즉 더 이상 내려갈 노드가 없음
        while(true){
            if(idx * 2 > size){
                break;
            }
            else if(idx * 2 == size){
                if(comp.compareTo((E) array[getLeftChild(idx)]) < 0){
                    break;
                }
                else{
                    // swap
                    E temp = (E) array[idx];
                    array[idx] = array[getLeftChild(idx)];
                    array[getLeftChild(idx)] = temp;
                    break;
                }
            }
            else {
                // 자식 노드 비교용 comp
                Comparable<? super E> compChild = (Comparable<? super E>) (E) array[getLeftChild(idx)];

                // 자식 노드들 중 우선순위가 높은 노드 찾기
                int minChild = compChild.compareTo((E) array[getRightChild(idx)]) >= 0 ? getRightChild(idx) : getLeftChild(idx);

                // 비교
                if (comp.compareTo((E) array[minChild]) <= 0) {
                    break;
                }

                // swap
                E temp = (E) array[idx];
                array[idx] = array[minChild];
                array[minChild] = temp;

                // heap down
                idx = minChild;
            }
        }
    }

    @SuppressWarnings("unchecked")
    private void shiftDownComparator(E value, Comparator<? super E> comp){

        // 루트 노드부터 시작
        int idx = 1;

        // 자식 index 가 범위를 넘어가면 종료, 즉 더 이상 내려갈 노드가 없음
        while(true){
            if(idx * 2 > size){
                break;
            }
            else if(idx * 2 == size){
                if(comp.compare(value, (E) array[getLeftChild(idx)]) < 0){
                    break;
                }
                else{
                    // swap
                    E temp = (E) array[idx];
                    array[idx] = array[getLeftChild(idx)];
                    array[getLeftChild(idx)] = temp;
                    break;
                }
            }
            else {
                // 자식 노드들 중 우선순위가 높은 노드 찾기
                int minChild = comp.compare((E) array[getLeftChild(idx)],(E) array[getRightChild(idx)]) >= 0 ? getRightChild(idx) : getLeftChild(idx);

                // 비교
                if (comp.compare(value ,(E) array[minChild]) <= 0) {
                    break;
                }

                // swap
                E temp = (E) array[idx];
                array[idx] = array[minChild];
                array[minChild] = temp;

                // heap down
                idx = minChild;
            }
        }
    }

 

2.4 기타 기능(size(), peek(), isEmpty(), toArray())

    public int size(){
        return this.size;
    }
    
    @SuppressWarnings("unchecked")
    public E peek(){
        if(array[1] == null)
            throw new NoSuchElementException();
        return (E) array[1];
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
    
    public Object[] toArray(){
        return Arrays.copyOf(array, size+1);
    }