Heap, Priority Queue, HashTable 이해하기

힙, 우선순위 큐, 해시 테이블 이해하기

코딩 테스트를 준비할 때마다, Heap, Priority Queue, HashTable 같은 자료구조를 인터넷 글들을 간단히 보고 사용하고 치우는게 효율적이지않아 정리하는 글입니다.

힙(Heap)

힙은 완전 이진 트리를 기반으로 한 자료구조로, 각 노드가 자식 노드보다 작거나 같은(Min Heap) 또는 크거나 같은(Max Heap) 값을 가집니다. 우선순위 큐 구현에 이상적입니다.
최대값 또는 최소값을 빠르게 찾아내야 할 때 유용한 완전 이진 트리 기반의 자료구조입니다.

주요 연산

• insert(key): 새로운 요소를 힙에 추가합니다.
• extractMax() / extractMin(): 힙에서 최댓값 또는 최솟값을 제거하고 반환합니다.
• peek(): 힙의 최댓값 또는 최솟값을 조회하지만 제거하지는 않습니다.

코딩 테스트에서의 활용

• 동적 데이터 집합에서 최댓값 또는 최솟값 접근이 자주 필요할 때:
  실시간으로 데이터가 추가/제거되며, 이 중 최댓값 또는 최솟값을 빠르게 접근해야 하는 경우
• 우선순위가 있는 작업 스케줄링이 필요할 때:
  작업들이 우선순위를 가지고 있으며, 우선순위가 가장 높은 작업부터 처리해야 하는 경우

우선순위 큐(Priority Queue)

우선순위 큐는 요소들이 우선순위에 따라 정렬되는 자료 구조로, 우선순위가 가장 높은 요소부터 차례대로 제거됩니다.
자바에서는 java.util.PriorityQueue 클래스를 통해 이 자료 구조를 제공하고 있으며, 내부적으로는 보통 힙(heap) 구조를 사용하여 구현됩니다.

주요 연산과 시간 복잡도

• add(element) 또는 offer(element): 우선순위에 따라 요소를 삽입합니다. 시간 복잡도는 O(log n)입니다.
• poll(): 우선순위가 가장 높은 요소를 제거하고 반환합니다. 시간 복잡도는 O(log n)입니다.
• peek(): 우선순위가 가장 높은 요소를 조회합니다(제거하지 않음). 시간 복잡도는 O(1)입니다.

우선 순위 정의 방법

우선순위를 정의하는 방법은 다양하며, 주로 람다식이나 Comparator 인터페이스를 사용합니다. 여기 몇 가지 예제를 소개합니다:

숫자 비교 (오름차순/내림차순)

• 오름차순 우선 순위 : 가장 낮은 숫자가 높은 우선순위를 갖습니다.

  PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
  

• 내림차순 우선 순위 : 가장 높은 숫자가 높은 우선순위를 갖습니다.

  PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
  

문자열 길이 비교

• 짧은 문자열 우선순위: 문자열 길이가 짧은 것이 높은 우선순위를 갖습니다.

  PriorityQueue<String> byLength = new PriorityQueue<>((a, b) -> a.length() - b.length());
  

• 긴 문자열 우선순위: 문자열 길이가 긴 것이 높은 우선순위를 갖습니다.

  PriorityQueue<String> byLengthDesc = new PriorityQueue<>((a, b) -> b.length() - a.length());
  

복잡한 객체 비교

• 객체의 특정 필드를 기준으로 우선순위를 정할 수 있습니다. 예를 들어, 사람(Person) 객체가 있고, 이를 나이(age)를 기준으로 우선순위를 정하려면:

class Person {
    String name;
    int age;
}

PriorityQueue<Person> byAge = new PriorityQueue<>((a, b) -> a.age - b.age);

복합 조건 비교

• 때로는 여러 조건을 결합하여 우선순위를 정의할 필요가 있습니다. 예를 들어, 사람 객체를 나이가 같을 경우 이름의 알파벳 순으로 정렬하고 싶다면:

PriorityQueue<Person> complexOrder = new PriorityQueue<>((a, b) -> {
    if (a.age == b.age) return a.name.compareTo(b.name);
    else return a.age - b.age;
});

코딩 테스트에서의 활용

• 다양한 요소들 중에서 우선순위에 따라 처리 순서를 결정해야 할 때:
  예를 들어, 여러 사용자의 요청을 우선순위에 따라 처리하거나, 네트워크 트래픽을 관리할 때 유용합니다.
• 그래프 알고리즘에서 최소 비용 문제를 해결해야 할 때:
  다익스트라 알고리즘과 같이 최소 비용 또는 최소 시간으로 목적지에 도달하는 경로를 찾는 문제에 적합합니다.

해시 테이블(HashTable)

해시 테이블은 키를 값에 매핑하는데 사용되는 자료구조입니다. 해시 함수를 사용해 키를 배열 인덱스로 변환하고, 이 인덱스를 사용해 값을 저장 또는 검색합니다.
빠른 데이터 검색, 삽입, 삭제를 가능하게 합니다.

주요 연산

• put(key, value): 주어진 키에 값을 저장합니다.
• get(key): 주어진 키에 해당하는 값을 조회합니다.
• remove(key): 주어진 키와 그 키에 해당하는 값을 해시 테이블에서 제거합니다.

코딩 테스트에서의 활용

• 데이터에 대한 빠른 접근이 필요할 때:
  예를 들어, 사용자 ID로 사용자 정보를 빠르게 검색해야 하는 경우
• 중복 체크나 빈도수 계산이 필요할 때:
  문자열 내의 문자 빈도수 계산이나, 배열 내의 중복 요소 검사 등 데이터의 특성을 분석할 때 유용합니다.