[Data Structure] heap

1. 힙(heap)이란?

참고 
https://geunuk.tistory.com/86
https://juhee-maeng.tistory.com/94

 

힙(heap)이란, 우선순위 큐를 위해 만들어진 자료구조의 완전 이진 트리의 일종이다.

데이터를 효율적으로 저장하고 최대값이나 최소값을 빠르게 찾기위해 고안되었다. 

 

※ 완전 이진 트리

완전 이진 트리는 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리

 

2. 힙의 연산

• 삽입
  • 새로운 노드의 힙을 마지막 위치에 추가
  • 부모 노드와 비교하며 위로 올림
• 삭제
  • 루트 노드 제거하고 마지막 루트로 이동
  • 자식 노드와 비교하며 아래로 내림
• 생성
  • 주어진 배열을 힙으로 변환

삽입과  삭제의 시간 복잡도는 O(log N), 생성은 O(N)이다.

 

3. 힙의 종류

• 최대 힙
  • 최대값을 빠르게 찾아내는 최대 트리이면서 완전 이진 트리
  • 부모 노드가 자식 노드보다 크거나 같음
• 최소 힙
  • 최소값을 빠르게 찾아내는 최소 트리이면서 완전 이진 트리
  • 부모 노드가 자식 노드보다 작거나 같음

 

4. Python - heapq

파이썬 내장모듈인 heapq를 사용하면 힙에 대한 문제를 쉽게 풀 수 있다.

백준 문제 최대 힙, 최소 힙, 절댓값 힙 문제를 풀어보자. 

 

백준 문제

1927 최소 힙 : https://www.acmicpc.net/problem/1927

11279 최대 힙 : https://www.acmicpc.net/problem/11279

11286 절댓값 힙 : https://www.acmicpc.net/problem/11286

 

import heapq
import sys

heap = []

n = int(sys.stdin.readline())

 

heapq 를 import 해주고 heap을 저장할 리스트 heap을 선언한다. 세 문제 전부 동일하게 n값을 입력받아준다.

 

최소 힙

for _ in range(n):
    # 입력 받기
    x = int(sys.stdin.readline())
    
    if x != 0:
        # 힙에 x값 넣기
        heapq.heappush(heap, x)
    else:
        # 힙이 비어있지 않으면 최댓값 출력, 아니면 0
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)

 

x를 입력 받고 0이 아니면 heap에 값을 추가한다 (heappush(리스트, 값)).

x 값으로 0을 입력 받았을 경우 heap이 비어있지 않으면 heap에 있는 최소값을 빼와서 값을 출력한다 (heappop(리스트)).

heapq에서는 값을 넣고 뺀 리스트 자체가 최소 힙이기 때문에 제일 위에 있는 값을 빼면 된다.

 

최대 힙

for _ in range(n):
    # 입력 받기
    x = int(sys.stdin.readline())
    
    if x != 0:
        # 힙에 -x 값 넣기
        heapq.heappush(heap, -x)
    else:
        # 힙이 비어있지 않으면 최댓값 출력, 아니면 0
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)

 

heapq 모듈은 최소 힙만 지원하기 때문에 리스트에 저장할 x값을 음수로 바꿔주면 최대 힙 로직을 구현할 수 있다.

음수로 바꾼 x값을 리스트에 저장하고 최소 힙과 마찬가지로 힙이 비어있지 않을 경우 음수로 저장한 값에 다시 - 를 더해 양수로 바꿔준 후 출력한다.

 

절댓값 힙

for _ in range(n):
	# 힙에 x값 넣기
    x = int(sys.stdin.readline())
    
    # 0이 아닐 경우 x의 절댓값과 x값을 함께 저장
    if x != 0:
        heapq.heappush(heap, (abs(x), x))
    else:
        if heap:
            print(heapq.heappop(heap)[1]) # x의 절댓값이 최소인 x 값을 출력
        else:
            print(0)

 

절댓값 힙은 조금 헷갈렸다. x값이 0이 아닐 경우 heap에 x의 절댓값과 x값을 튜플로 저장한다.

heap이 비어있지 않을 경우 x의 절댓값을 기준으로 정렬된 x값을 출력한다.

 

※ 튜플(Tuple)

여러 값을 순서대로 저장하는 자료구조

 

 

 

 

감사합니다 ヾ(•ω•`)o