자료구조 ] 힙(Binary Heaps) - 최소힙(Min-Heaps), 최대힙(Max-Heaps) 개념 정리

1. 힙(Heap)이란?

 - 힙이란 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 완전 이진트리를 기본으로 한 자료구조이다.

2. 최소힙(Min-Heaps)과 최대힙(Max-Heaps)에 차이

 - '이미지 1'에서 최소 힙은 저장된 숫자중 'ROOT'에 최소값을 배치한다. 힙에 새로운 숫자가 추가가되면 부모 노드와 비교를 해서 작은 숫자가 'ROOT'를 향해 교체된다.

이미지 1] 최소 힙

예시 : '?' 위치 노드에 신규숫자 5가 추가가 되면 부모노드인 7보다 작은 숫자이기 때문에 서로 교체가된다. 이런 과정을 거쳐 제일 작은 최소값이 'ROOT'로 향해 정렬되게 되는 것이다.

 

이미지 2] 최대 힙

 - 최대 힙은 최소 힙의 반대로 정렬로 생각하면 된다.

3. Java 우선순위큐(PriorityQueue)

 - 자바에서는 힙 방식으로 이미 구현된 우선순위 큐를 제공하고 있다.

 

//최소힙
public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.offer(4);
    priorityQueue.offer(2);
    priorityQueue.offer(1);

    System.out.println(priorityQueue); // result : [1,4,2]
}

 - 최소갑을 제일 앞 공간으로 배치기 때문에 1이 제일 앞에 있다.

//최대힙
public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

    priorityQueue.offer(4);
    priorityQueue.offer(2);
    priorityQueue.offer(1);

    System.out.println(priorityQueue); // result : [4,2,1]
}

 - 최대갑을 제일 앞 공간으로 배치기 때문에 4가 제일 앞에 있다.