파이썬 백준 1927번 : 최소 힙

문제 

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

풀이

sol1) 우선순위 큐 사용

import sys
from queue import PriorityQueue
N = int(sys.stdin.readline())
queue= PriorityQueue()
for _ in range(N):
    n=int(sys.stdin.readline())
    if(n==0):
        if queue.empty():
            print('0')
            continue
        print(queue.get())
    else:
        queue.put(n)

 

---

우선순위 큐

생성

queue = PriorityQueue() #size는 무한대
queue = PriorityQueue(maxsize=10) # size를 10으로 설정

 

데이터 추가

queue.put(7) #오름차순으로 우선순위 부여
queue.put((1, 'ONE')) #우선순위를 지정하고 싶으면 queue.put((우선순위, value))로 작성

 

데이터 삭제

queue.get()
print(queue.get()) # 삭제한 값은 반환됨

 

우선순위 큐 확인 메서드

queue.qsize() #큐의 크기 확인
queue.empty() # 큐가 비어있는지 확인
queue.full() # 큐가 꽉 찼는지 확인

 

sol2) 힙사용

import sys
import heapq
heap=[] #힙 생성
N= int(sys.stdin.readline())
for _ in range(N):
    x=int(sys.stdin.readline())
    if x==0:
        if len(heap)==0:
            print('0')
            continue
        print(heapq.heappop(heap))
    else:
        heapq.heappush(heap,x)

heqpq를 사용한 했을때 실행시간이 더 적었다 

---

heapq과 PriorityQueue의 차이

1. 내부 구현 방식:
   • heapq 모듈은 이진 힙(binary heap)을 사용하여 우선순위 큐를 구현. 힙은 각 노드가 부모 노드보다 작은(또는 큰) 값을 갖도록 정렬된 이진 트리.
     삽입과 삭제 연산의 시간 복잡도는 O(log n) 
   • PriorityQueue 클래스는 내부적으로 힙을 사용하지만, 이는 독립적인 클래스로서 구현. -> 추가적인 레이어가 존재, 좀 더 복잡한 인터페이스를 제공.
2. 오버헤드:
   • heapq 모듈은 파이썬의 내장 모듈로서 오버헤드가 거의 없음
   • PriorityQueue 클래스는 스레드 세이프하게 설계. -> 동시성을 지원하려면 추가적인 락(lock)이 필요하며, 이로 인해 약간의 오버헤드가 발생가능.
3. 메모리 사용:
   • heapq 모듈은 리스트를 사용하여 힙을 구현 ->  메모리 사용량이 상대적으로 적습니다.
   • PriorityQueue 클래스는 사용하는 자료구조에 따라 추가적인 메모리를 소모할 수 있음.( ex 링크드 리스트(linked list)나 배열) 메모리 사용량을 늘릴 수 있음

---

힙 

특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리

• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

import heapq로 사용할 수 있다.

• heapq.heappush(heap, item) : item을 heap에 추가  ( O(logN) 소요 )
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop (반환값 있음. 비어 있는 경우 IndexError)  ( O(logN) 소요 )
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환 (O(N)소요 )