[자료구조] 우선순위 큐와 힙

우선순위 큐(Priority Queue)란?

• 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조
• 큐(Queue)가 선입선출(FIFO) 원칙을 따르는 반면, 우선순위 큐는 우선순위에 따라 요소의 처리 순서가 결정

특징

• 우선순위가 높은 요소가 먼저 처리됨
• 동일한 우선순위를 가진 요소는 일반적으로 선입선출

사용 사례

• 작업 스케줄링
• 다익스트라 알고리즘
• 허프만 코딩

예시 코드

기본 우선순위 큐 구현

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 요소 추가
        pq.offer(10);
        pq.offer(5);
        pq.offer(20);

        // 우선순위 큐 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 작은 값부터 출력
        }
    }
}

커스텀 우선순위 큐 구현

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 추가
        maxHeap.offer(10);
        maxHeap.offer(5);
        maxHeap.offer(20);

        // 우선순위 큐 출력
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 큰 값부터 출력
        }
    }
}

 

---

힙(Heap)이란?

• 우선순위 큐를 구현하기 위해 가장 널리 사용되는 자료구조
• 힙은 완전 이진 트리로 구성
  • 최대 힙(Max-Heap) : 부모 노드가 자식 노드보다 크거나 같음
  • 최소 힙(Min-Heap) : 부모 노드가 자식 노드보다 작거나 같음

힙의 주요 연산

• 삽입(Insertion) : 새 요소를 추가
• 삭제(Deletion) : 루트 요소(최대값 또는 최소값)를 제거
• 힙 생성(Heapify) : 배열을 힙으로 변환

시간 복잡도

• 삽입: O(log n)
• 삭제: O(log n)
• 힙 생성: O(n)

예시 코드

힙과 배열의 관계 힙은 배열을 사용해 구현할 수 있음

• 부모 노드 인덱스 : (i-1)/2
• 왼쪽 자식 노드 인덱스 : 2*i+1
• 오른쪽 자식 노드 인덱스 : 2*i+2

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp();
    }

    public int remove() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return root;
    }

    private void heapifyUp() {
        int index = size - 1;
        while (index > 0 && heap[(index - 1) / 2] > heap[index]) {
            int temp = heap[index];
            heap[index] = heap[(index - 1) / 2];
            heap[(index - 1) / 2] = temp;
            index = (index - 1) / 2;
        }
    }

    private void heapifyDown() {
        int index = 0;
        while (2 * index + 1 < size) {
            int smallerChild = 2 * index + 1;
            if (2 * index + 2 < size && heap[2 * index + 2] < heap[smallerChild]) {
                smallerChild = 2 * index + 2;
            }
            if (heap[index] < heap[smallerChild]) {
                break;
            }
            int temp = heap[index];
            heap[index] = heap[smallerChild];
            heap[smallerChild] = temp;
            index = smallerChild;
        }
    }
}

우선순위 큐와 힙의 관계

• 우선순위 큐는 힙 외에도 배열이나 연결 리스트로 구현할 수 있지만, 힙을 사용하면 효율적으로 작동
• 특히 삽입과 삭제 연산이 빈번한 경우, 힙을 사용하면 최적의 성능을 보장할 수 있음

---

면접 대비 질문

기본 질문

Q1. 우선순위 큐란 무엇이며, 일반적인 큐와의 차이점은 무엇인가요?

• 우선순위 큐는 요소의 우선순위에 따라 처리 순서가 결정되는 자료구조입니다. 일반적인 큐는 선입선출(FIFO)을 따르지만, 우선순위 큐는 높은 우선순위 요소가 먼저 처리됩니다.

Q2. 힙의 주요 연산과 시간 복잡도는 무엇인가요?

• 삽입과 삭제는 O(log n), 힙 생성은 O(n)입니다.

Q3. 힙 자료구조를 사용하는 대신 이진 탐색 트리를 사용할 경우 장단점은 무엇인가요?

• 장점:
  1. 탐색 효율성: 이진 탐색 트리는 정렬된 상태로 데이터를 저장하므로 특정 값을 찾는 데 O(log n)의 시간 복잡도를 가집니다.
  2. 범위 쿼리: 이진 탐색 트리는 정렬된 순서를 유지하기 때문에 범위 쿼리(예: 특정 범위의 값들을 찾기)와 같은 작업이 용이합니다.
• 단점:
  1. 삽입 및 삭제 성능: 힙은 삽입과 삭제가 O(log n)로 일정하지만, 이진 탐색 트리는 트리의 균형 상태에 따라 O(n)까지 성능이 저하될 수 있습니다.
  2. 구현 복잡성: 균형 이진 탐색 트리(예: AVL 트리, 레드-블랙 트리)를 유지하려면 추가적인 로직이 필요하며, 힙보다 구현이 복잡합니다.
  3. 최댓값/최솟값 접근: 힙은 최댓값(또는 최솟값)을 O(1)에 접근할 수 있지만, 이진 탐색 트리는 O(log n) 시간이 필요합니다.

심화 질문

Q1. 힙 정렬의 원리와 시간 복잡도를 설명해주세요.

• 힙 정렬은 힙을 사용해 배열을 정렬하는 알고리즘으로, 최대 힙 또는 최소 힙을 구성한 후 요소를 하나씩 꺼내 정렬합니다. 시간 복잡도는 O(n log n)입니다.

Q2. 배열로 구현된 힙에서 특정 인덱스의 부모나 자식 노드를 찾는 방법을 설명해주세요.

• 부모 노드: (i-1)/2, 왼쪽 자식 노드: 2*i+1, 오른쪽 자식 노드: 2*i+2

Q3.힙에서 특정 요소를 효율적으로 삭제하려면 어떤 방법을 사용할 수 있나요? (예: 인덱스 맵핑을 사용한 최적화)

• 일반적으로 힙은 특정 요소를 삭제하기 위해 O(n)의 순회 시간이 필요합니다. 그러나 인덱스 맵핑(해시맵)을 사용하면 삭제 연산을 효율적으로 수행할 수 있습니다.
  1. 요소와 해당 요소의 힙 내 인덱스를 저장하는 해시맵을 추가로 유지합니다.
  2. 삭제 요청 시 해시맵에서 인덱스를 즉시 찾습니다(O(1)).
  3. 힙에서 해당 인덱스의 요소를 삭제한 후, 마지막 요소를 해당 위치로 이동시키고 힙 구조를 복구합니다(힙 속성 유지).
• 이 방법은 해시맵의 추가 공간이 필요하지만, 삭제의 시간 복잡도를 O(log n)으로 줄일 수 있습니다.

Q4. 힙 정렬은 안정적인 정렬인가요? 그 이유는 무엇인가요?

• 힙 정렬은 안정적인 정렬이 아닙니다.
• 이유:
  1. 힙 정렬은 힙 구조를 사용하여 데이터를 정렬하는 과정에서 같은 값의 상대적 순서를 보존하지 않습니다.
  2. 루트 노드를 제거하거나 힙 속성을 복원하는 과정에서 같은 값을 가진 요소들의 원래 순서가 뒤바뀔 수 있습니다.
• 만약 안정성을 보장하려면 값 외에 추가 정보를 저장하거나, 비교 시 우선순위와 삽입 순서를 함께 고려해야 합니다.

압박 질문

Q1. 우선순위 큐에서 특정 요소를 찾거나 삭제하려면 어떻게 해야 하나요?

• 기본적으로 우선순위 큐는 루트 요소(최대값/최소값)에 대한 삽입과 삭제를 효율적으로 지원하지만, 특정 요소를 찾거나 삭제하려면 큐를 순회해야 하므로 시간 복잡도는 O(n)입니다.

Q2. 다익스트라 알고리즘에서 우선순위 큐를 사용하는 이유는 무엇인가요?

• 다익스트라 알고리즘에서는 가장 짧은 경로를 가진 노드를 효율적으로 선택하기 위해 우선순위 큐를 사용합니다. 이를 통해 시간 복잡도를 O((V+E) log V)로 줄일 수 있습니다.

Q3. 멀티스레드 환경에서 우선순위 큐를 구현할 때 발생할 수 있는 문제와 이를 해결하기 위한 방법은 무엇인가요?

• 문제:
  1. 데이터 경합(Race Condition): 여러 스레드가 동시에 큐에 삽입하거나 삭제할 때 데이터의 일관성이 깨질 수 있습니다.
  2. 동시성 제약: 하나의 스레드가 큐를 사용하고 있을 때 다른 스레드가 대기해야 하므로 성능이 저하될 수 있습니다.
• 해결 방법:
  1. 동기화 사용: synchronized 블록이나 ReentrantLock을 사용해 큐에 대한 접근을 동기화합니다.
  2. 동시성 라이브러리 사용: 자바의 java.util.concurrent.PriorityBlockingQueue와 같은 동시성 지원 자료구조를 사용하면 별도의 동기화 없이 멀티스레드 환경에서 안전하게 작동합니다.
  3. 락 분할: 큐를 여러 개의 파티션으로 나누어 병렬로 접근할 수 있도록 설계합니다.
  4. 비차단 알고리즘: 비교적 복잡하지만, CAS(Compare-and-Swap)를 기반으로 한 비차단 알고리즘을 사용할 수 있습니다.

Q4. 배열 기반 힙에서 메모리 사용량을 줄이기 위한 방법은 무엇이 있을까요?

• 배열 기반 힙의 메모리 사용량을 줄이기 위해 다음과 같은 최적화 기법을 사용할 수 있습니다:
  1. 동적 배열 크기 조정: 초기 크기를 작게 설정하고, 필요에 따라 배열 크기를 늘리거나 줄이는 방식을 사용합니다.
     • 예: Java의 ArrayList처럼 요소 추가 시 크기를 두 배로 늘리고, 사용량이 낮을 경우 배열 크기를 줄이는 방식.
  2. 압축 저장: 값의 범위가 작다면, 더 작은 데이터 타입(예: int 대신 short 또는 byte)을 사용하여 메모리 사용량을 줄입니다.
  3. 인덱스 기반 접근 최적화: 트리 구조를 메모리 효율적으로 저장하기 위해 완전 이진 트리의 성질을 활용하여 인덱스 계산만으로 관계를 유지합니다.
  4. 외부 저장소 활용: 메모리 부족 문제가 심각한 경우, 일부 데이터를 디스크로 오프로드하고 필요한 경우 다시 로드하는 방식(예: 외부 정렬)을 사용할 수 있습니다.