[자료구조 & 알고리즘] 10. 힙, 우선순위 큐

힙, 우선순위 큐

1. 힙 (Heap)

• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 형태의 자료구조

• 최대값을 빠르게 찾기 위한 최대 힙과 최소값을 빠르게 찾기 위한 최소 힙이 있음.

• Max Heap (최대 힙)

     - 부모 노드의 값이 자식 노드의 값보다 큼.

     - root 노드가 가장 큼.

• Min Heap (최소 힙)

     - 부모 노드의 값이 자식 노드의 값보다 작음.

     - root 노드가 가장 작음.

• 값을 삽입 및 삭제할 때마다 트리를 재정렬하여 부모 자식 간의 대소관계를 올바르게 함.

     - 삽입 : 완전 이진 트리의 마지막에 노드 삽입 -> 부모와 대소 관계를 비교하여 서로 자리를 바꾸는 것을 반복. O(log n)의 시간 복잡도

     - 삭제 : 완전 이진 트리의 루트 노드 삭제 -> 마지막 노드를 루트 노드로 바꿈 -> 자식과 대소 관계를 비교하여 서로 자리를 바꾸는 것을 반복. O(log n)

     - 즉, 삽입과 삭제 모두 O(log n)이 걸림.

• 형제 노드 간에는 대소 관계가 정해지지 않음.

• 리스트로 표현 가능

     - 완전 이진 트리는 리스트로 표현 가능하다는 특성이 있음.

     - 힙 역시 완전 이진 트리이기 때문에 리스트로 표현이 가능.

     - 예를 들어, 위와 같은 힙은 {100, 34, 68, 20, 27, 13, 56, 7, 18}과 같은 리스트로 저장이 가능.

     - 리스트의 인덱스가 i인 노드가 있다면 그 노드의 자식은 2i + 1, 2i + 2임.

     - 리스트의 인덱스가 i인 노드가 있다면 그 노드의 부모는 (i-1) / 2 임.

     - 원래의 트리는 마지막 노드를 탐색하기 위해 노드를 순차적으로 탐색해야 하지만, 리스트로 표현하여 마지막 노드에 직접 접근할 수 있도록 함.

 

2. 우선순위 큐 (Priority Queue)

• 가장 높은 우선순위를 가진 데이터가 큐에서 먼저 추출되는 자료구조.

• 구현 방법

     1. 배열을 이용한 구현

          - 정렬을 하지 않은 배열

               - enqueue : 들어오는 순서대로 배열에 저장. O(1)

               - dequeue : 우선순위를 검색하여 꺼냄. + 요소가 빠진 위치에 뒷 요소들을 당겨 채움. O(n)

          - 정렬한 배열

               - enqueue : 들어올 때마다 정렬하여 저장. O(n log n)

               - dequeue : 순서대로 꺼냄. O(1)

          => 배열을 이용하면 O(n)이나 O(n log n) 만큼의 큰 시간 복잡도가 필요하고, enqueue와 dequeue의 밸런스가 맞지 않음.

     2. 힙을 이용한 구현

          - enqueue : 힙의 삽입. O(log n)

          - dequeue : 힙의 삭제. O(log n)

     => 힙을 이용하면 enqueue와 dequeue 모두 밸런스있게 O(log n)의 적은 시간 복잡도가 걸림.

• 자바의 우선순위 큐

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최소힙은 그냥 사용
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> -Integer.compare(o1, o2)); // 최대힙은 Comparator 이용하여 일반적인 비교 결과에 -1 곱하면 됨.