힙(Heap)이란?

완전 이진 트리의 일종으로, 최솟값(최소 힙) 또는 최댓값(최대 힙)을 빠르게 찾고 관리하기 위해 고안된 자료구조

❓완전 이진 트리는 무엇일까?

루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식노드 순으로 데이터가 차례대로 삽입되는 트리

(출처: https://heytech.tistory.com/105)

최소 힙 vs 최대 힙

• 최소 힙
  - 루트 노드가 가장 작은 값을 가짐
  • 값이 작은 데이터가 우선적으로 삭제
• 최대 힙
  - 루트 노드가 가장 큰 값을 가짐
  • 값이 큰 데이터가 우선적으로 삭제

힙의 사용

1. 빠른 우선순위 처리
   • 최솟값 또는 최댓값을 빠르게 탐색 가능
   • 삽입과 삭제 연산이 효율적
2. 정렬 효율성
   • 힙 정렬의 최악의 경우 O(nlogn)의 시간 복잡도
3. 메모리 효율성
   • 완전 이진 트리 구조로 배열을 사용해 구현하여 메모리 오버헤드가 적음
4. 동적 데이터 관리
   • 동적으로 변화하는 데이터에 대해 효율적으로 최솟값 또는 최댓값을 효율적으로 관리

힙의 동작

힙의 연산 과정을 알아보자.
최소 힙으로 예를 들자.

• 삽입
  

1. 8 삽입
2. 10 삽입
   • 10이 왼쪽 최하단 노드에 삽입되고 부모와 비교
   • 부모인 8과 비교했을 때 10이 더 크므로 이 자리에 위치
3. 6 삽입
   • 6이 오른쪽 최하단 노드에 삽입되고 부모와 비교
   • 부모인 8과 비교했을 때 6이 더 작으므로 위치를 교체
4. 13 삽입
   • 13이 왼쪽 최하단 노드에 삽입되고 부모와 비교
   • 부모인 10과 비교했을 때 크므로 이 자리에 위치

• 삭제
  최소 힙을 예로 들어 삭제해보자.
  
  (출처: https://innovation123.tistory.com/111)

1. 루트노드인 1 삭제
2. 마지막 노드를 루트노드로 변경
3. 새로운 루트노드인 4와 자식노드인 3과 2중 더 작은 값인 2와 변경
4. 루트노드는 2가되고 4인 노드는 다시 자식노드인 5와 3중 작은 값인 3으로 변경(5는 4보다 크기때문에 고려하지 않음)

힙에 대해 알아봤으니 우선순위 큐(Priority Queue)에 대해 알아보자.

우선순위 큐(Priority Queue)란?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

• 데이터를 우선순위에 따라 처리 가능(병원 대기실에서 환자들은 상태에 따라 우선순위가 매겨져, 응급 환자가 먼저 진료를 받는 구조)

List vs Heap

리스트와 힙 중 어떤 방법이 효율적일까?

• 데이터 개수를 N개라고 하자
  • 리스트는 삽입시간이 O(1)이지만 삭제시간은 O(N)
  • 힙은 삽입시간 삭제시간 모두 O(logN)

💡따라서 우선순위 큐를 구현할 때 힙(heap)이 더 효율적이다.

Code

자바(java)에서 우선순위 큐(priority queue)를 사용하여 힙(heap)을 구현해보자.

• 최소 힙

PriorityQueue<Integer> queue = new PriorityQueue<>();

queue.add(5);
queue.add(3);
queue.add(8);
queue.add(1);
queue.add(4);

while (!queue.isEmpty()){
    System.out.print(queue.poll()+" ");
}
// 출력: 1 3 4 5 8

• 최대 힙
  - Collections.reverseOrder()를 사용하여 내림차순으로 정렬

PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
queue.add(5);
queue.add(3);
queue.add(8);
queue.add(1);
queue.add(4);
while (!queue.isEmpty()) {
    System.out.print(queue.poll() + " ");
}
// 출력: 8 5 4 3 1