[자료구조] 힙, 최소힙, 최대힙, heapq(python)

1. 힙(heap)이란?

• 가장 높은 우선순위를 가지는 노드를 빠르게 찾을 수 있는 자료구조
• 저장된 값이 힙 조건(완전이진트리, 루트노드의 우선순위가 제일 높아야 됨)을 만족하는 리스트
• 최대 힙(Max Heap) : 부모 노드 key > 자식 노드 key
• 최소 힙(Min Heap) : 부모 노드 key < 자식 노드 key

2. heapq

• import heapq 를 이용해서 모듈 import
• heap = [] #힙으로 사용할 list 생성
• 삽입 연산 : heappush(heap명, item)
• 삭제 연산 : heappop(heap명)
• heap는 최소힙만 지원됨

 

추가)

heapq 의 내부 동작 원리를 알고 싶으면 신찬수 교수님의 자료구조 강의 참고하기(https://youtu.be/8XnPN6IB22Y)

heapq 의 함수는 후술하는 링크 참고하기 (https://www.daleseo.com/python-heapq/)

 

 

heap 관련 문제들

백준 1927번 최소힙 (실3) O

백준 11279번 최대힙 (실3) O

백준 11286번 절댓값 힙(실1) O

백준 1715번 카드 정렬하기 (골4) O

백준 7662번 이중 우선순위 큐 (골4)

백준 1655번 가운데를 말해요 (골2)

 

해결한 문제

1. 백준 1927번 최소힙 (실3)

 

import heapq
import sys

input = sys.stdin.readline

n = int(input().rstrip()) #연산의 개수

heap = []

for i in range(n):
  x = int(input().rstrip())
  if x == 0:
    if len(heap) > 0:
      print(heapq.heappop(heap))
    else:
      print(0)
  
  else:
    heapq.heappush(heap,x)

 

2. 백준 11279번 최대힙 (실3)

 

import heapq
import sys

input = sys.stdin.readline

n = int(input().rstrip()) #연산의 개수

heap = []

for i in range(n):

  x = int(input().rstrip()) 

  if x == 0:
    if len(heap) > 0: #원소의 부호를 바꿔서 pop
      print(-heapq.heappop(heap))
    else:
      print(0)

  else: #원소의 부호를 바꿔서 push
    heapq.heappush(heap,-x)

 

3. 백준 11286번 절댓값 힙 (실1)

 

from re import X
import heapq

n = int(input()) #연산 횟수

heap = []
result = []
for i in range(n):
  x = int(input())
  y = (abs(x),x)

  if x == 0:
    if len(heap) > 0:
      print(heapq.heappop(heap)[1])
    else:
      print(0)

  else:
    heapq.heappush(heap, y)

 

4. 백준 1715번 카드 정렬하기 (골4)

 

import heapq
import sys

input = sys.stdin.readline

n = int(input().rstrip()) #입력 횟수

heap = []

for i in range(n):
  heapq.heappush(heap,int(input().rstrip()))

answer = 0

while True:

  if len(heap) > 1:
    result = 0
    result = heapq.heappop(heap) + heapq.heappop(heap)
    answer += result
    heapq.heappush(heap, result)
    
  if len(heap) == 1:
    break

print(answer)