[CT] Heap

Kyungmin·2024년 2월 8일

heap python 힙

CodingTest_Python

목록 보기

1/12

자바에서 PriorityQueue pq = new PriorityQueue<>() 이 있어서 그걸로는 이미 한번 구현해보았던 문제였는데 파이썬으로는 처음 문제를 풀어보았다.

같은 문제지만 언어가 달라서 아직 파이썬에 적응중인 단계..

힙❓

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

📎 최소 힙

1. 최소 힙

'''
최소 힙
'''
import sys
import heapq

n = int(sys.stdin.readline())
heap = []
for i in range(n):
    shot = int(sys.stdin.readline())
    if shot == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, shot)

    # 정수를 넣는데 0이면 현재 힙에서 제일 작은 것 출력
    # 아니라면 힙에 삽입

2. 최대 힙

📎 최대 힙

'''
최대 힙
'''
import sys
import heapq

n = int(sys.stdin.readline())
heap = []
for i in range(n):
    shot = int(sys.stdin.readline())
    if shot == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, -shot)

파이썬에서는 '최대 힙' 을 지원하지 않는다.
따라서 최소 힙으로 푼다음 부호만 다르게 해주어 순서를 최소 힙처럼 만들어준다.

📝 heapq.nlargest(k,nums)

import heapq 를 하여 사용 가능한 파이썬의 라이브러리
k 번째 가장 큰요소를 찾아줌

heapq.nlargest(k, nums) 함수는 배열 nums에서 가장 큰 k개의 요소를 찾아서 리스트로 반환한다. 이 리스트는 내림차순으로 정렬된다.
heapq 모듈은 힙 큐 알고리즘, 특히 최소 힙을 기반으로 작동하는 여러 함수를 제공한다. 그러나 heapq.nlargest() 함수를 사용하여 이 경우에는 최대 힙처럼 작동하여 주어진 배열에서 k번째로 큰 값을 효율적으로 찾을 수 있다.