[자료구조] 최소힙 / 최대힙

알고리즘

[자료구조] 최소힙 / 최대힙

Jay_J 2024. 10. 17. 13:26

최소힙과 최대힙에 대한 설명

힙(Heap)은 이진 트리 기반의 자료구조로, 특정한 규칙을 따릅니다. 힙에는 두 가지 주요 형태가 있습니다:

1. 최소힙(Min Heap): 부모 노드의 값이 자식 노드보다 항상 작거나 같은 이진 트리입니다. 즉, 가장 작은 값이 루트에 위치하게 됩니다.

2. 최대힙(Max Heap): 부모 노드의 값이 자식 노드보다 항상 크거나 같은 이진 트리입니다. 가장 큰 값이 루트에 위치합니다.

이 두 힙은 주로 우선순위 큐(Priority Queue)로 사용되며, 값을 정렬된 순서대로 유지해야 하는 문제를 해결하는 데 매우 효율적입니다.

최소힙의 특징

• 가장 작은 값을 빠르게 찾고 싶을 때 유용합니다.

• 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다.

• 파이썬에서는 heapq 라이브러리를 사용해 최소힙을 구현할 수 있습니다.

최대힙의 특징

• 가장 큰 값을 빠르게 찾고 싶을 때 유용합니다.

• 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다.

• 파이썬의 heapq는 기본적으로 최소힙으로 동작하므로, 최대힙을 구현하려면 음수로 변환해서 사용합니다.

최소힙/최대힙을 사용하는 상황

1. 우선순위가 있는 작업 처리

• 힙은 우선순위 큐(Priority Queue)로 사용되며, 가장 높은(작거나 큰) 우선순위를 가진 요소를 빠르게 처리해야 할 때 매우 유용합니다.

• 예시: 병원 응급실, 작업 스케줄링 등 우선순위가 있는 작업을 먼저 처리할 때.

2. K번째 최소/최대 값을 구할 때

• 힙을 사용하면 K번째로 작은/큰 값을 찾는 연산을 매우 효율적으로 할 수 있습니다.

• 최소/최대 값을 찾아야 하는 문제에서는 힙이 시간 복잡도를 크게 줄여줍니다.

3. 실시간으로 가장 큰 값이나 작은 값을 관리할 때

• 데이터가 계속해서 추가될 때, 매번 최소값이나 최대값을 빠르게 추적해야 할 경우 힙이 유용합니다.

• 예시: 스트리밍 데이터에서 상위 K개의 값을 추적하는 문제.

4. 정렬된 데이터를 유지해야 할 때

• 힙을 사용하면 데이터를 정렬된 상태로 유지하면서도 삽입/삭제가 빠릅니다.

• 예시: 실시간으로 정렬된 데이터를 처리하는 알고리즘.

최소힙/최대힙의 사용 예시

최소힙 예시:

import heapq

h = []

heapq.heappush(h, 5)

heapq.heappush(h, 3)

heapq.heappush(h, 8)

print(heapq.heappop(h)) # 3, 최소값부터 꺼내짐

print(heapq.heappop(h)) # 5

print(heapq.heappop(h)) # 8

최대힙 예시 (음수를 이용):

import heapq

h = []

heapq.heappush(h, -5) # 음수로 저장하여 최대힙 구현

heapq.heappush(h, -3)

heapq.heappush(h, -8)

print(-heapq.heappop(h)) # 8, 최대값을 꺼내려면 다시 양수로 변환

print(-heapq.heappop(h)) # 5

print(-heapq.heappop(h)) # 3

힙을 사용하면 효율적인 경우

• 데이터가 계속해서 들어오고, 그중 가장 큰 값이나 가장 작은 값을 실시간으로 추적해야 하는 경우.

• 데이터가 계속 추가되지만 매번 전체를 정렬할 필요는 없고, 가장 큰 값이나 작은 값만 찾고 싶을 때.

• K번째로 큰 값/작은 값을 구하는 문제를 효율적으로 해결하고 싶을 때.

비효율적인 경우

• 이미 정렬된 배열이 주어졌을 때 굳이 힙을 사용할 필요가 없습니다.

• 힙의 삽입과 삭제는 O(log n)이므로, 단순 정렬이 더 나은 선택일 수 있는 경우도 있습니다.

최소힙/최대힙의 시간 복잡도

• 삽입 및 삭제: O(log n)

• 최소/최대값 조회: O(1) (루트 노드이기 때문에 바로 조회 가능)

힙은 실시간 데이터 처리나 우선순위가 중요한 문제에서 매우 효율적이므로 이러한 문제를 해결할 때 사용하는 것이 좋습니다.

예시 :

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

3 ≤ k ≤ 100
7 ≤ score의 길이 ≤ 1,000
- 0 ≤ score[i] ≤ 2,000

입출력 예kscoreresult

3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

아래와 같이, [0, 0, 0, 0, 20, 40, 70, 70, 150, 300]을 return합니다.

이 문제는 루프를 돌며 매 루프마다 최솟값을 찾아야 한다. 또한, 매번 스택을 업데이트 해줘야 하는데, 최솟값을 배열의 맨 마지막에 넣어야 한다. 힙이 없다면, 매 루프마다 append -> 배열을 정렬해야 한다. 하지만 정렬의 시간 복잡도는 O(n log n)이므로 큰 입력에 대해서는 비효율적이다.

어차피 이 문제에서 우리가 찾아야 하는건 '최솟값' 이다.

루프가 n번 돌고, 매번마다 리스트를 정렬하고 거기서 최솟값을 찾는건 비효율적이다. 따라서, 힙을 쓰면 실시간으로 따로 정렬이나 min()함수 없이 최솟값을 트래킹 할 수 있다.

import heapq

def solution(k, score):
    answer = []
    h = []
    
    for s in score:
        if len(h) < k:
            heapq.heappush(h, s)  # 힙에 값 추가
        else:
            # 현재 힙의 최솟값보다 큰 경우 힙의 최솟값을 대체
            if h[0] < s:
                heapq.heapreplace(h, s)  # 가장 작은 값을 pop하고 s 삽입
        answer.append(h[0])  # 현재 힙에서 최솟값을 answer에 추가
        
    return answer

질문 1: h[0]이 최솟값인가?

• 최소힙에서 h[0]은 항상 최소값이다. 파이썬의 heapq 라이브러리는 기본적으로 최소힙을 사용하므로, 가장 작은 값이 루트에 위치합니다.

• 따라서 h[0]은 최소값을 의미한다.

질문 2: heapreplace가 뭐냐?

• heapq.heapreplace(h, s)는 최소힙에서 가장 작은 값(루트 노드)을 꺼낸 뒤, 새로운 값을 힙에 추가하는 함수다. 즉, 기존의 최솟값을 삭제하고, 새로운 값을 삽입하는 연산이다.

• 이 함수는 다음과 같은 두 가지 동작을 하나의 연산으로 처리한다:

1. 최소값을 꺼냄 (heappop(h))

2. 새로운 값을 삽입 (heappush(h, s))

이 과정에서 힙은 여전히 최소힙의 조건을 만족하게끔 유지된다.

예시:

import heapq

h = [1, 3, 5, 7, 9]

heapq.heapreplace(h, 4)

print(h)  # 출력: [3, 4, 5, 7, 9]

1. h에서 최소값 1이 삭제되고, 4가 삽입되었다.

2. 결과적으로 힙의 최소값은 3으로 바뀌었고, 힙의 다른 요소들은 최소힙의 조건을 만족하도록 재정렬되었다.

heapreplace()와 heappushpop()의 차이:

• heapreplace()는 값을 무조건 삭제한 후 새로운 값을 삽입.

• 반면에, heappushpop()은 새로운 값을 먼저 힙에 삽입한 뒤, 가장 작은 값(루트 노드)을 제거하는 방식으로 동작. 삽입하는 값이 힙의 최솟값보다 작으면, 그대로 그 값이 빠지고 힙은 그대로 유지.

예시 비교:

import heapq

h = [1, 3, 5, 7, 9]

# heapreplace: 기존 최솟값을 삭제하고 4를 삽입

heapq.heapreplace(h, 4)

print(h)  # 출력: [3, 4, 5, 7, 9]

# heappushpop: 먼저 2를 삽입하고 최솟값을 제거

heapq.heappushpop(h, 2)

print(h)  # 출력: [3, 4, 5, 7, 9] (2는 최솟값이기 때문에 삽입되자마자 빠짐)

따라서, heapreplace()는 값 대체가 필요한 경우 사용되고, heappushpop()은 삽입한 값이 최소값일 때 효율적으로 처리할 수 있는 방법입니다.