[Python] 백준 1927번 : 최소 힙

해당 글은 백준사이트의 1927번 문제를 풀고 배운 내용을 정리한 글입니다.

문제 url: https://www.acmicpc.net/problem/1927

 

백준 1927번 문제를 통해 힙 자료구조에 대해 공부해보자. 

1. 힙 (Heap) 이란?

정의:
힙은 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 크거나 작다는 특성을 가집니다. 최소 힙(min-heap)에서는 부모 노드가 자식 노드보다 작고, 최대 힙(max-heap)에서는 부모 노드가 자식 노드보다 큽니다.

특징:
힙은 우선순위 큐의 구현에 자주 사용됩니다.
삽입과 삭제 연산이 O(log n)의 시간 복잡도를 가집니다.
힙을 사용하면 우선순위 큐의 효율적인 구현이 가능합니다

2. 최소 힙 (Min-Heap) 이란?

특징
완전 이진 트리: 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 오른쪽으로 채워져 있습니다.
힙 속성: 각 노드의 값이 그 자식 노드의 값보다 작거나 같은 특성을 가집니다. 즉, 부모 노드의 값은 자식 노드의 값보다 항상 작거나 같아야 합니다. 이로 인해 최소 힙의 루트 노드는 항상 가장 작은 값을 가지게 됩니다.

주요연산
최소 힙은 주로 우선순위 큐(Priority Queue) 구현에 사용되며, 다음과 같은 연산을 효율적으로 수행할 수 있습니다:
삽입: 새로운 요소를 힙에 추가하는 연산. 평균적으로 O(log n)의 시간 복잡도를 가집니다.
최소값 추출: 힙에서 가장 작은 값을 제거하고 반환하는 연산. 이 또한 O(log n)의 시간 복잡도를 가집니다.
최소값 조회: 힙의 루트 노드에 있는 최소값을 조회하는 연산. O(1)의 시간 복잡도를 가집니다. 

 

3. 우선순위 큐( Priority Queue )란?

정의:
우선순위 큐는 데이터가 들어간 순서와 관계없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.
즉, 각 데이터는 우선순위를 가지며, 우선순위가 높은 데이터가 먼저 처리됩니다

특징:
우선순위가 같은 경우, 들어온 순서에 따라 처리될 수 있습니다.
일반적으로 최소 힙(min-heap) 또는 최대 힙(max-heap)으로 구현됩니다.
다양한 알고리즘에서 사용되며, 예를 들어 다익스트라 알고리즘에서 최단 경로를 찾는 데 활용됩니다

 

힙 (Heap)	완전 이진 트리의 일종으로, 특정한 힙 속성을 가진 자료구조.	부모 노드와 자식 노드 간의 관계에 따라 정렬됨.
최소 힙 (Min-Heap)	부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리.	루트 노드가 항상 최소값을 가짐.
우선순위 큐 (Priority Queue)	각 요소에 우선순위를 부여하여, 높은 우선순위를 가진 요소가 먼저 처리되는 큐.	일반 큐와 달리 우선순위에 따라 요소가 처리됨.
힙 큐 (Heap Queue)	힙을 기반으로 구현된 우선순위 큐.	삽입 및 삭제 연산이 O(log n) 시간 복잡도를 가짐.

 

4. 문제풀이

백준 1927번 문제는 최소 힙을 구현하는 문제. 주어진 N개의 연산을 통해 자연수를 힙에 삽입하거나, 힙에서 가장 작은 값을 추출하는 작업을 수행. 입력 형식은 첫 줄에 연산의 개수 N이 주어지고, 그 다음 N줄에 각각의 연산이 주어진다.

 

1) 우선순위 queue

class MyPriorityQueue:
    def __init__(self):
        self.data = []
    
    # 아이템을 리스트에 추가
    def push(self, item):
        self.data.append(item)  
        self.data.sort()
    
    def pop(self):
        if self.data:
            return self.data.pop(0)
        return 0


import sys

# 모든 입력 값 한번에 받기
input = sys.stdin.read
data = input().splitlines()
N = int(data[0])

# 사용자 정의 우선순위 큐 인스턴스 생성
pq = MyPriorityQueue()

for i in range(1, N + 1):
    num = int(data[i])
    if num > 0:
        pq.push(num)
    else:
        smallest = pq.pop()
        print(smallest)

1. 입력 처리:
   • 첫 번째 입력으로 연산의 수 N을 읽습니다.
   • 이후 N개의 정수를 차례로 읽습니다.
2. 우선순위 큐 관리:
   • 양수인 경우 리스트에 추가하고 정렬하여 최소 힙 특성을 유지합니다.
   • 0이 입력되면 리스트의 첫 번째 요소(가장 작은 수)를 제거하고 결과 리스트에 추가합니다. 리스트가 비어있다면 0을 추가합니다.

 

2) heapq

import heapq, sys
input = sys.stdin.readline

hq = []
N = int(input())
for _ in range(N):
    now = int(input())
    if now == 0:
        if hq:
            print(heapq.heappop(hq))
        else:
            print(0)
    else:
        heapq.heappush(hq, now)

1. 입력 처리:
   • 첫 번째 입력으로 연산의 수 N을 읽습니다.
   • 이후 N개의 정수를 차례로 읽습니다.
2. 힙 관리:
   • 양수인 경우 heapq.heappush()를 사용하여 힙에 추가합니다.
   • 0이 입력되면 힙에서 가장 작은 수를 heapq.heappop()으로 꺼내어 결과 리스트에 추가합니다.