python data library - heapq) 많은 데이터에서 최소값 또는 최대값을 빨리 찾는 방법

 

프로그래머스 - 더 맵게 

---

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

처음 생각했던 방법

def solution(scoville, K):
    scoville.sort(reverse=True)
    answer = 0
    while scoville[-1] < K:
        if len(scoville) > 1:
            scoville.append(scoville.pop() + 2 * scoville.pop())
            scoville.sort(reverse=True)
            answer += 1
        else:
            return -1
    return answer

최소 힙을 이용한 문제 해결 

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    time = 0
    while scoville[0] < K:
        if len(scoville) > 1:
            heapq.heappush(scoville, heapq.heappop(scoville)+heapq.heappop(scoville)*2)
            time += 1
        else:
            return -1
    return time

 

 

 

 

힙 큐 알고리즘

---

 

이 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공하고 있습니다. 힙은 최소 힙과 최대 힙으로 구분되며 최소 힙과 같은 경우에는 제일 작은 숫자를 루트로 크기가 작은 순대로 정렬된 이진트리로 구현됩니다. 그 와 반대로 최대 힙은 제일 큰 숫자를 루트로 만든 후 크기가 큰 순대로 정렬된 이진트리로 구현됩니다.

 

파이썬 라이브러리의 heapq 라이브러리는 최소 힙을 이용하고 있습니다. heapq로 만들어진 heap 리스트가 있다면 heap[0]은 가장 작은 항목이 될 것이고, heap.sor0를 사용해도 힙의 불변성을 유지할 수 있습니다.

 

힙을 만드려면, []로 초기화된 리스트를 사용해서 하나씩 push 하는 방법도 존재하고, 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 반환할 수 있습니다. 

 

heappush()를 이용한 힙 생성 

    heap = []
    for i in scoville:
        heapq.heappush(heap, i)

 heapify()를 이용한 리스트를 힙으로 변경(생성)

 heapq.heapify(scoville)

 

 

 

메서드

---

heapq.headpush(heap, item)	힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.
heapq.heappop(heap)	힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError 가 발생합니다.
heapq.heappushpop(heap, item)	힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 이 액션은 이 함수는 push 함수화 pop함수를 별도로 호출한 것 보다 효율적으로 사용할 수 있습니다.
heapq.heapify(x)	리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.
heapq.heapreplace(heap, item)	heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시합니다. 힙 크기는 변경되지 않습니다.  힙이 비어 있으면, IndexError 가 발생합니다. 이 액션 또한 heappushpop()처럼 효율적으로 사용할 수 있습니다.
heapq.merge(*iterables, key=None, reverse=False)	여러 정렬된 입력을 단일 정렬된 출력으로 병합합니다. sorted(itertools.chain(*iterables))와 비슷하지만 이터러블을 반환하고, 데이터를 한 번에 메모리로 가져오지 않으며, 각 입력 스트림이 이미 (최소에서 최대로) 정렬된 것으로 가정합니다. key는 각 입력 요소에서 비교 키를 추출하는 데 사용되는 단일 인자의 키 함수를 지정합니다. 기본값은 None입니다 (요소를 직접 비교합니다).
heapq.nlargest(n, iterable, key=None)	terable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환합니다. key가 제공되면 iterable의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정합니다
heapq.nsmallest(n, iterable, key=None)	iterable에 의해 정의된 데이터 집합에서 n 개의 가장 작은 요소로 구성된 리스트를 반환합니다. key가 제공되면 iterable의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정합니다
마지막 두 함수 nlargest(), nsmallest()는 작은 n 값에서 가장 잘 동작합니다. 값이 크면, sorted() 기능을 사용하는 것이 더 효율적입니다.

 

 

heapq.heappushpop(heap, item)

heapq.heappush(scoville, heapq.heappop(scoville)+heapq.heappop(scoville)*2)

위의 메서드를 이용하면 위의 코드를 아래와 같이 이용할 수 있습니다. 

        min1 = heapq.heappop(scoville)
        min2 = heapq.heappushpop(scoville, min2 + min1 + min1)

 

 

 

docs.python.org/ko/3.10/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.0a5 문서