Heap 자료구조

힙 자료구조란 우선순위 큐를 위하여 만들어진 완전 이진트리의 일종이다.

큐는 선입선출 구조가 이루어지는 자료구조이다.

이에 데이터들에게 우선순위를 주는 것이다.

여러 값들 중 최댓값과 최솟값을 찾기 용이하고 느슨한 정렬 상태를 유지한다.

<왼쪽 이미지는 최대힙>.  <오른쪽 이미지는 최소힙 >

최대 힙의 경우에는 최상단 부모 노드에 최대값이, 최소힙의 경우에는 최상단 부모노드에 최솟값이 와야 한다.

최대 힙의 경우 자식 노드의 값들은 부모 노드보다 클 수 없고 최소 힙은 그 반대이다.

 

파이썬은 heapq를 import 해서 간편하게 사용이 가능하다.

원소를 삽입시) heapq.heappush(리스트 이름, value)

원소 제거 시 heapq.heappop(리스트 이름) : 가장 작은 값 출력

heap 자료구조로 변환) heapq/heapify(리스트 이름)

 

파이썬의 heapq는 기본적으로 최소 힙 형태이다.

만약 최대 힙을 만들고 싶다면 아래와 같다.

import heapq
import sys

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


heap = []

for i in range(n):
    x = int(sys.stdin.readline())

    if x == 0:
        if len(heap) != 0:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap,(-x,x))

-x를 기준으로 최소 힙 정렬을 하면 절댓값이 가장 큰 x가 가장 작을 것이기에 실제로는 가장 큰 값이 가장 앞에 오게 된다.

따라서 heappop을 배열의 1번째 원소를 기준으로 하게 되면 최댓값이 나오게 된다.