힙과 우선순위 큐

문득 JVM의 힙과 자료구조의 힙이 왜 이름이 똑같을까? 하는 궁금증이 생겼다가 자료구조 힙에 대한 개념을 다 잊어버려서 정리한다.

힙이란?

힙 : 데이터에서 최대값, 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙은 언제, 왜 사용해?

힙은 최대값, 최소값을 빠르게 찾기 위해 사용된다.

• 배열의 경우 최대값, 최소값을 찾는데 $O(n)$ 이 걸린다.
• 힙의 경우 최대값, 최소값을 찾는데 $O(logn$) 이 걸린다.
  => 따라서 최대값, 최소값을 찾기 위해 '힙' 을 사용한다.

우선순위 큐와 같이 최대값, 최소값을 빠르게 찾아야하는 자료구조, 알고리즘 구현에 활용된다.

• 즉, '힙' 자료구조로 우선순위 큐를 구현한다.
• 배열, 리스트로 구현하는 것보다 시간 복잡도가 더 낮기에 힙으로 구현한다.

힙(Heap) 구조

힙은 크게 두 가지 구조로 나눌 수 있다.

• 최대 힙(Max Heap) : 최대값을 구하기 위한 구조
• 최소 힙(Min Heap) : 최소값을 구하기 위한 구조

힙은 두 가지 조건을 가진다.

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙 기준)
   • 즉, 루트 노드 값이 제일 크다 (레벨이 0에 가까울 수록 값이 크다.)
   • 최소 힙은 최대 힙과 반대로 생각하면 된다. 즉, 루트 노드 값이 제일 작다.
2. 완전 이진 트리 형태를 가진다.
   • 즉, 왼쪽 최하단부 노드부터 채워지는 형태로 삽입된다.

힙과 이진 탐색 트리 비교

둘 다 자료구조 형태는 비슷해보이지만, 차이점도 존재한다.

비교	힙	이진 탐색 트리
공통점	이진 트리 이다.
차이점 - 최대, 최소값이 트리의 어디에 위치하는가?	- 최대 힙 기준으로, 각 노드의 값이 자식 노드보다 크거나 같다. (즉, 루트 노드로 갈수록 값이 크다.)	- 왼쪽, 가운데, 오른쪽 노드 순서로 값이 커진다. (즉, 루트 노드로 갈수록 값이 커지는 것이 아니라, 왼-> 오로 갈수록 값이 크다.)
차이점 - 자식 노드 중 큰 값이 왼쪽, 오른쪽 중 어디에 위치하는가?	- 이진 탐색 트리와 달리 힙은 자식 노드에서 큰 값이 왼쪽에 있을 수도, 오른쪽에 있을 수도 있다. (즉, 부모 노드보다 작기만 하면 된다.)	- 이진 탐색 트리의 조건에 따라, 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른 쪽에 위치한다.
차이점 - 그래서 주로 언제 쓰이는가?	- 최대, 최소값을 빠르게 찾기위해 쓰인다.	- 이름 그대로 '탐색'을 위해 쓰인다.
차이점 - 자바에서는 어떻게 구현되는가?	- 우선순위 큐 (Priority Queue)로 구현된다.	- TreeSet, TreeMap으로 구현되었다.
차이점 - 중복 허용	- 우선순위 큐를 사용할 때 , 동일한 값이 add 된다면 모든 값을 출력했을 때 동일한 값이 입력된 만큼 출력된다. 즉 중복값을 허용한다.  (예를 들어 1을 두번 add 했으면 1이 두번 출력된다.)	- TreeSet, TreeMap을 사용할 때, 동일한 값이 add 된다면 모든 값을 출력했을 때 딱 한번만 출력된다. (예를 들어 1을 두번 add 하더라도 출력은 한 번만 된다.)

 

추가적으로, 이진 탐색 트리는 자바의 TreeSet, TreeMap으로 구현되었다.

힙의 데이터 삽입, 삭제

그렇다면 힙에서는 데이터 삽입, 삭제가 어떻게 이뤄질까?

데이터 삽입

• 추가하는 데이터가 부모 노드보다 클 경우(최대힙) : 일단 최하단의 비어있는 노드로 채운 후, 최대 힙 기준을 충족할 때까지 swap

데이터 삭제

• 보통 삭제는 최상단 노드(root)를 삭제하는 것이 일반적이다. (애초에 힙은 최대, 최소값 찾기 위해 쓰이기 때문)
• 상단의 데이터 삭제 시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동한다.
• root 노드의 값이 자식 노드보다 작을 경우 swap을 반복한다.

힙을 구현한 우선순위 큐(Priority Queue) 사용 방법

자바에서는 우선순위 큐로 힙을 구현하였다.
실제 코드에서는 어떻게 쓰이는지 간단하게 살펴보겠다.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);

        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // 출력: 1, 2, 3
        }
    }
}

 

기본적으로 우선순위 큐는 최소 힙을 사용한다. 만약 최대힙을 사용하고 싶으면 Comparator를 지정할 수 있다.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

이진 탐색 트리를 구현한 TreeSet, TreeMap 사용 방법

추가적으로 , 함께 언급되었던 이진 탐색 트리를 구현한 TreeSet, TreeMap도 코드로 어떻게 사용되는지 궁금하여 찾아보았다.

 

TreeSet

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(2);

        System.out.println(treeSet); // 출력: [1, 2, 3]
    }
}

 

TreeMap

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("three", 3);
        treeMap.put("one", 1);
        treeMap.put("two", 2);

        System.out.println(treeMap); // 출력: {one=1, three=3, two=2}
    }
}

 

 

 

당장 코드를 통해 보더라도 Queue, Set은 요소를 추가할 때 add를 쓰고 Map은 put을 사용한다. 

컬렉션 프레임워크에 대한 구조를 이해해야 각자의 메서드도 헷갈리지 않게 쓸 수 있을 듯하여,... 

우선순위 큐에 사용할 수 있는 다양한 메서드들은 추후에 자바의 컬렉션 프레임워크에 대해 다뤄보면서 한번에 정리해보겠습니다. (제발)