파이썬 백준 11279번 : 최대 힙

문제 

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

11279번: 최대 힙

 

 

풀이

sol1) 우선순위 큐 이용

import sys
from queue import PriorityQueue
queue=PriorityQueue() #우선순위 큐 선언

N= int(sys.stdin.readline())
for _ in range(N):
    x=int(sys.stdin.readline())
    if x==0:
        if queue.empty():
            print('0')
            continue
        print(abs(queue.get())) #절댓값으로 출력 
    else:
        queue.put(-x) #최대힙 구현을 위해 값에 -를 붙여 queue에 넣기

 

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(abs(heapq.heappop(heap)))
    else:
        heapq.heappush(heap,-x)

 

파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸렸다.

 

 

---

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)소요 )