DataStructure/Tree

힙(Heap), 우선순위 큐(Priority Queue)의 원리와 구현

Lazy_developer 2023. 2. 28. 22:07

들어가며

  • 힙(Heap)은 최대, 최소값이 항상 루트로 존재하는 트리이다.
  • 힙 트리는 다음과 같은 특징을 가진다.
    • 힙 트리의 루트는 최대값(최대 힙일때), 최소값(최소 힙일때) 중 하나의 값을 가진다.
    • 힙 구조에서 부모 노드는 자식 노드보다 작거나(최소 힙일때) 커(최대 힙일떄)야 한다.
    • 힙 트리는 완전 이진 트리이다.
    • 트리에 데이터가 들어가거나 삭제될 때 최대 최소값만 가장 위로 올라가는 구조이며 그 이외에는 정렬되어있지 않다. 이를 반정렬 상태라고 한다.
    • 중복된 값이 들어갈 수 있다.
  • 루트가 항상 최소가 되게 하는 힙을 최소 힙(min heap)이라고 하며 루트가 항상 최대가 되게 하는 힙을 최대 힙(max heap)이라고 한다.

 

 

힙의 구현

  • 이번에 구현할 힙은 최소 힙으로 구현하며 다음과 같은 연산을 가진다.
    • 데이터의 삽입
    • 데이터의 삭제
    • 힙의 요소 출력
  • 힙은 완전 이진 트리의 특성을 가지기 때문에 배열로 손쉽게 구현이 가능하다.
  • 기본적힌 힙의 구조는 다음과 같다.
import java.util.*;

// min Heap
class MyHeap{
    ArrayList<Integer> heap;

    MyHeap(){
        heap = new ArrayList<>();
        heap.add(-1);
    }

    public void add(int data){
        
    }

    public int remove(){
        
    }

    public void printTree(){
        for (int i = 1; i < heap.size(); i++){
            System.out.print(heap.get(i) + " ");
        }
        System.out.println();
    }
}

 

 

 

힙의 자료 삽입

  • 힙의 자료 삽입은 다음과 같이 이루어진다.
    • 완전 이진 트리의 특성에 맞게 데이터를 삽입한다. 즉 좌에서 우로 데이터를 삽입한다.
    • 이후 삽입한 위치부터 부모 노드와 값을 비교해 위치를 변경한다. 위치를 변경함으로서 힙의 부모 노드는 자식 노드보다 작아야 한다 라는 조건을 충족시키게 된다.
  • 아래와 같은 트리에서 6을 삽입했다. 완전 이진 트리의 특성에 맞게 삽입한 것을 볼 수 있다.

최소 힙에서 노드의 삽입

  • 이후 부모 노드는 자식 노드보다 작아야 한다는 원칙을 지키기 위해 부모 노드와 값을 비교한다.
  • 여기서는 25와 값을 비교하며 25보다 작으므로 두 노드의 위치(값)을 바꾸게 된다.

위치가 바뀐 후의 힙

  • 이제 다시 부모와 비교하며 부모보다 큰 위치가 생길 때 까지 위치를 이동한다.

완전히 이동이 끝난 최소 힙

  • 이러면 최소 힙에서 노드의 삽입이 완료되었다.
  • 이를 코드로 구현하면 아래와 같다.
public void add(int data){
    heap.add(data);

    int cur = heap.size() - 1;

    // heap 에 들어간 데이터가 루트가 아니고 부모보다 내가 작은 동안 나는 위로 올라간다.
    while(cur > 1 && heap.get(cur / 2) > heap.get(cur)){
        int parentValue = heap.get(cur / 2);

        // swap
        heap.set(cur / 2, data);
        heap.set(cur, parentValue);

        // 이동했을 시 위치 갱신
        cur /= 2;
    }
}
  • 완전 이진 트리 구조에서 어떤 인덱스가 있을 때 인덱스 / 2를 수행한 위치는 해당 노드의 부모 노드임을 기억하라
  • 해당 사항만 인지하면 나머지는 위에서 설명한 그대로를 구현한 것에 불과하다.

 

 

 

힙에서 자료의 삭제

  • 힙에서 자료를 삭제하는 방법은 아래와 같이 이루어진다.
    • 루트에 존재하는 값을 반환하고 힙에서 가장 마지막에 삽입된 데이터를 루트에 넣는다.
    • 이후 최소 힙에 맞도록 비교하며 데이터의 위치를 이동시킨다.
  • 이때 좌측 자식만 있는경우, 두 자식이 존재하는 경우의 2가지 케이스가 있다.
    • 좌측 자식만 존재하는 경우 좌측 자식쪽으로 데이터의 위치를 내려보낸다.
    • 두 자식이 존재하는 경우 두 자식 중 더 작은 값을 가진 자식과 데이터를 비교하고 위치를 교환한다.

예시 트리

  • 해당 힙에서 자료를 삭제해보자.6을 반환하고 마지막에 위치한 25를 루트로 올리게 된다.

위치 교환 직후의 힙

  • 이제 부모 노드의 값이 자식 노드보다 작도록 위치를 재조정한다. 이때 25는 두 자식 10, 30이 있는데 이 경우 위에서 서술한 것 처럼 10과 30중 더 작은 값과 비교하게 된다. 즉 10과 비교하게 된다.
  • 10이 25보다 작기 때문에 25와 10은 위치를 변경한다.

  • 이후 내려간 위치에서 다시 자식과 비교를 수행한다. 두 자식이 있기 떄문에 15, 18 중 더 작은 값과 비교하게 되며 15가 더 작기 때문에 위치를 바꾸게 된다

  • 이를 코드로 옮기면 다음과 같다.
public int remove(){
    if (this.heap.size() == 1){
        return -1;
    }

    int data = this.heap.get(1);

    this.heap.set(1, heap.get(heap.size() - 1));
    this.heap.remove(heap.size() - 1);

    int cur = 1;

    while(true){
        int left = cur * 2;
        int right = cur * 2 + 1;
        int location = -1;

        if (right < heap.size()){
            location = heap.get(left) < heap.get(right) ? left : right;
        } else if (left < heap.size()){
            location = left;
        } else{
            break;
        }

        if (heap.get(cur) < heap.get(location)){
            break;
        } else{
            int parentVal = heap.get(cur);

            heap.set(cur, heap.get(location));
            heap.set(location, parentVal);

            cur = location;
        }
    }

    return data;
}

 

 

 

정리

  • 최소 힙은 자료의 삽입과 삭제에서 부모 노드는 자식 노드보다 그 크기가 작아야 한다 라는 원칙만을 지키면서 구현하면 어렵지 않다.
  • 최대 힙은 크기 비교를 정 반대로만 하면 되므로 구현에 크게 어렵지 않을 것이다.
  • 전체적인 코드는 다음과 같다.
import java.util.*;

// min Heap
class MyHeap{
    ArrayList<Integer> heap;

    MyHeap(){
        heap = new ArrayList<>();
        heap.add(-1);
    }

    public void add(int data){
        heap.add(data);

        int cur = heap.size() - 1;

        // heap 에 들어간 데이터가 루트가 아니고 부모보다 내가 작은 동안 나는 위로 올라간다.
        while(cur > 1 && heap.get(cur / 2) > heap.get(cur)){
            int parentValue = heap.get(cur / 2);

            // swap
            heap.set(cur / 2, data);
            heap.set(cur, parentValue);

            // 이동했을 시 위치 갱신
            cur /= 2;
        }
    }

    public int remove(){
        if (this.heap.size() == 1){
            return -1;
        }

        int data = this.heap.get(1);

        this.heap.set(1, heap.get(heap.size() - 1));
        this.heap.remove(heap.size() - 1);

        int cur = 1;

        while(true){
            int left = cur * 2;
            int right = cur * 2 + 1;
            int location = -1;

            if (right < heap.size()){
                location = heap.get(left) < heap.get(right) ? left : right;
            } else if (left < heap.size()){
                location = left;
            } else{
                break;
            }

            if (heap.get(cur) < heap.get(location)){
                break;
            } else{
                int parentVal = heap.get(cur);

                heap.set(cur, heap.get(location));
                heap.set(location, parentVal);

                cur = location;
            }
        }

        return data;
    }

    public void printTree(){
        for (int i = 1; i < heap.size(); i++){
            System.out.print(heap.get(i) + " ");
        }
        System.out.println();
    }
}

public class StudyCode {
    public static void main(String[] args){
        MyHeap heap = new MyHeap();

        heap.add(10);
        heap.add(25);
        heap.add(24);
        heap.add(13);
        heap.add(7);

        heap.printTree();

        System.out.println(heap.remove());
        System.out.println(heap.remove());

        heap.printTree();
    }
}
저작자표시 (새창열림)