Heap

Heap

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리

heap 사용 이유

• 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림, 시간 단축
  -> 배열에 데이터를 넣고 최대값, 최소값 찾으려면 O(n)이 걸림
• 힙을 사용하면 항상 정렬된 상태로 추가되고 삭제 됨
  -> 힙에서 가장 작은값은 언제나 인덱스 0, 이진 트리의 루트에 위치함

heapq 모듈

import heapq

heapq는 내장모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

import heapq
heap = []
heapq.heappush(heap,50)
heapq.heappush(heap,10)
heapq.heappush(heap,20)
#heap = [10,50,20]

heapq.heappush(heap,item): item을 heap에 추가

heap2=[50,10,20]
heapq.heapify(heap2)
#heap2=[10,50,20]

heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함, 시간복잡도 : O(n)

result = heapq.heappop(heap)
#result = 10
#heap=[20,50]

heapq.heappop(heap) : heap에서 가장 작은 원소를 히베서 제거함과 동시에 결괏값으로 리턴함. 비어 있는 경우 IndexError가 호출됨.

원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근하면 된다.

heap 기본적인 문제

최소힙

import heapq
import sys
input = sys.stdin.readline

n = int(input())
q=[]
for _ in range(n):
    c = int(input())

    if c ==0:
        if q:
            print(heapq.heappop(q))

        else:
            print(0)

    else:
        heapq.heappush(q, c)

최대 힙

import heapq
import sys
input = sys.stdin.readline

n = int(input())
q=[]
for _ in range(n):
    c= int(input())

    if c ==0:
        if q:
            print(-heapq.heappop(q))
        else:
            print(0)
    else:
        heapq.heappush(q,-c)

1. 최대힙을 구하려면 입력받는 숫자에 (-)를 붙혀 제일 큰 숫자를 최솟값으로 만든다
2. 그리고 heapq.heappop()을 할 때에 (-)를 붙혀 양수로 만들어 출력시킨다

절대값 힙

import heapq
import sys
input= sys.stdin.readline

n = int(input())
q=[]
for _ in range(n):
    c= int(input())

    if c ==0:
        if q:
            print(heapq.heappop(q)[1])
        else:
            print(0)

    else:
        heapq.heappush(q,(abs(c),c))

1. 절대값을 사용해 우선순위를 부여하고 힙큐에 튜플을 push 함
2. 값을 출력할때는 인덱스 번호로 값만 출력