"heapq" --- 힙 큐 알고리즘
**************************

**소스 코드:** Lib/heapq.py

======================================================================

이 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구
현을 제공합니다.

Min-heaps are binary trees for which every parent node has a value
less than or equal to any of its children. We refer to this condition
as the heap invariant.

For min-heaps, this implementation uses lists for which "heap[k] <=
heap[2*k+1]" and "heap[k] <= heap[2*k+2]" for all *k* for which the
compared elements exist.  Elements are counted from zero.  The
interesting property of a min-heap is that its smallest element is
always the root, "heap[0]".

Max-heaps satisfy the reverse invariant: every parent node has a value
*greater* than any of its children.  These are implemented as lists
for which "maxheap[2*k+1] <= maxheap[k]" and "maxheap[2*k+2] <=
maxheap[k]" for all *k* for which the compared elements exist. The
root, "maxheap[0]", contains the *largest* element;
"heap.sort(reverse=True)" maintains the max-heap invariant.

The "heapq" API differs from textbook heap algorithms in two aspects:
(a) We use zero-based indexing.  This makes the relationship between
the index for a node and the indexes for its children slightly less
obvious, but is more suitable since Python uses zero-based indexing.
(b) Textbooks often focus on max-heaps, due to their suitability for
in-place sorting. Our implementation favors min-heaps as they better
correspond to Python "lists".

These two aspects make it possible to view the heap as a regular
Python list without surprises: "heap[0]" is the smallest item, and
"heap.sort()" maintains the heap invariant!

Like "list.sort()", this implementation uses only the "<" operator for
comparisons, for both min-heaps and max-heaps.

In the API below, and in this documentation, the unqualified term
*heap* generally refers to a min-heap. The API for max-heaps is named
using a "_max"  suffix.

To create a heap, use a list initialized as "[]", or transform an
existing list into a min-heap or max-heap using the "heapify()" or
"heapify_max()" functions, respectively.

The following functions are provided for min-heaps:

heapq.heapify(x)

   Transform list *x* into a min-heap, in-place, in linear time.

heapq.heappush(heap, item)

   Push the value *item* onto the *heap*, maintaining the min-heap
   invariant.

heapq.heappop(heap)

   Pop and return the smallest item from the *heap*, maintaining the
   min-heap invariant.  If the heap is empty, "IndexError" is raised.
   To access the smallest item without popping it, use "heap[0]".

heapq.heappushpop(heap, item)

   힙에 *item*을 푸시한 다음, *heap*에서 가장 작은 항목을 팝하고 반환
   합니다. 결합한 액션은 "heappush()"한 다음 "heappop()"을 별도로 호출
   하는 것보다 더 효율적으로 실행합니다.

heapq.heapreplace(heap, item)

   *heap*에서 가장 작은 항목을 팝하고 반환하며, 새로운 *item*도 푸시합
   니다. 힙 크기는 변경되지 않습니다. 힙이 비어 있으면, "IndexError"가
   발생합니다.

   이 한 단계 연산은 "heappop()"한 다음 "heappush()"하는 것보다 더 효
   율적이며 고정 크기 힙을 사용할 때 더 적합 할 수 있습니다. 팝/푸시
   조합은 항상 힙에서 요소를 반환하고 그것을 *item*으로 대체합니다.

   반환된 값은 추가된 *item*보다 클 수 있습니다. 그것이 바람직하지 않
   다면, 대신 "heappushpop()" 사용을 고려하십시오. 푸시/팝 조합은 두
   값 중 작은 값을 반환하여, 힙에 큰 값을 남겨 둡니다.

For max-heaps, the following functions are provided:

heapq.heapify_max(x)

   Transform list *x* into a max-heap, in-place, in linear time.

   Added in version 3.14.

heapq.heappush_max(heap, item)

   Push the value *item* onto the max-heap *heap*, maintaining the
   max-heap invariant.

   Added in version 3.14.

heapq.heappop_max(heap)

   Pop and return the largest item from the max-heap *heap*,
   maintaining the max-heap invariant.  If the max-heap is empty,
   "IndexError" is raised. To access the largest item without popping
   it, use "maxheap[0]".

   Added in version 3.14.

heapq.heappushpop_max(heap, item)

   Push *item* on the max-heap *heap*, then pop and return the largest
   item from *heap*. The combined action runs more efficiently than
   "heappush_max()" followed by a separate call to "heappop_max()".

   Added in version 3.14.

heapq.heapreplace_max(heap, item)

   Pop and return the largest item from the max-heap *heap* and also
   push the new *item*. The max-heap size doesn't change. If the max-
   heap is empty, "IndexError" is raised.

   The value returned may be smaller than the *item* added.  Refer to
   the analogous function "heapreplace()" for detailed usage notes.

   Added in version 3.14.

이 모듈은 또한 힙 기반의 세 가지 범용 함수를 제공합니다.

heapq.merge(*iterables, key=None, reverse=False)

   여러 정렬된 입력을 단일 정렬된 출력으로 병합합니다 (예를 들어, 여러
   로그 파일에서 타임 스탬프 된 항목을 병합합니다). 정렬된 값에 대한 *
   이터레이터*를 반환합니다.

   "sorted(itertools.chain(*iterables))"와 비슷하지만 이터러블을 반환
   하고, 데이터를 한 번에 메모리로 가져오지 않으며, 각 입력 스트림이
   이미 (최소에서 최대로) 정렬된 것으로 가정합니다.

   키워드 인자로 지정해야 하는 두 개의 선택적 인자가 있습니다.

   *key*는 각 입력 요소에서 비교 키를 추출하는 데 사용되는 단일 인자의
   *키 함수*를 지정합니다. 기본값은 "None"입니다 (요소를 직접 비교합니
   다).

   *reverse*는 불리언 값입니다. "True"로 설정하면, 각 비교가 반대로 된
   것처럼 입력 요소가 병합됩니다. "sorted(itertools.chain(*iterables),
   reverse=True)"와 유사한 동작을 달성하려면 모든 이터러블이 최대에서
   최소로 정렬되어 있어야 합니다.

   버전 3.5에서 변경: 선택적 *key*와 *reverse* 매개 변수를 추가했습니
   다.

heapq.nlargest(n, iterable, key=None)

   *iterable*에 의해 정의된 데이터 집합에서 *n* 개의 가장 큰 요소로 구
   성된 리스트를 반환합니다. *key*가 제공되면 *iterable*의 각 요소에서
   비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정합니다 (예를 들
   어, "key=str.lower"). 다음과 동등합니다: "sorted(iterable, key=key,
   reverse=True)[:n]".

heapq.nsmallest(n, iterable, key=None)

   *iterable*에 의해 정의된 데이터 집합에서 *n* 개의 가장 작은 요소로
   구성된 리스트를 반환합니다. *key*가 제공되면 *iterable*의 각 요소에
   서 비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정합니다 (예를
   들어, "key=str.lower"). 다음과 동등합니다: "sorted(iterable,
   key=key)[:n]".

마지막 두 함수는 작은 *n* 값에서 가장 잘 동작합니다. 값이 크면,
"sorted()" 기능을 사용하는 것이 더 효율적입니다. 또한, "n==1"일 때는,
내장 "min()"과 "max()" 함수를 사용하는 것이 더 효율적입니다. 이 함수를
반복해서 사용해야 하면, iterable을 실제 힙으로 바꾸는 것이 좋습니다.


기본 예
=======

힙 정렬은 모든 값을 힙으로 푸시한 다음 한 번에 하나씩 가장 작은 값을
팝 하여 구현할 수 있습니다:

   >>> def heapsort(iterable):
   ...     h = []
   ...     for value in iterable:
   ...         heappush(h, value)
   ...     return [heappop(h) for i in range(len(h))]
   ...
   >>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

이것은 "sorted(iterable)"과 비슷하지만, "sorted()"와 달리, 이 구현은
안정적(stable)이지 않습니다.

힙 요소는 튜플일 수 있습니다. 추적하는 기본 레코드와 함께 비교 값(가령
작업 우선순위)을 지정하는 데 유용합니다:

   >>> h = []
   >>> heappush(h, (5, 'write code'))
   >>> heappush(h, (7, 'release product'))
   >>> heappush(h, (1, 'write spec'))
   >>> heappush(h, (3, 'create tests'))
   >>> heappop(h)
   (1, 'write spec')


Other Applications
==================

Medians are a measure of central tendency for a set of numbers.  In
distributions skewed by outliers, the median provides a more stable
estimate than an average (arithmetic mean).  A running median is an
online algorithm that updates continuously as new data arrives.

A running median can be efficiently implemented by balancing two
heaps, a max-heap for values at or below the midpoint and a min-heap
for values above the midpoint.  When the two heaps have the same size,
the new median is the average of the tops of the two heaps; otherwise,
the median is at the top of the larger heap:

   def running_median(iterable):
       "Yields the cumulative median of values seen so far."

       lo = []  # max-heap
       hi = []  # min-heap (same size as or one smaller than lo)

       for x in iterable:
           if len(lo) == len(hi):
               heappush_max(lo, heappushpop(hi, x))
               yield lo[0]
           else:
               heappush(hi, heappushpop_max(lo, x))
               yield (lo[0] + hi[0]) / 2

For example:

   >>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
   [5.0, 7.0, 5.0, 7.0, 8.0, 8.5]


우선순위 큐 구현 참고 사항
==========================

우선순위 큐는 힙의 일반적인 사용이며, 몇 가지 구현 과제가 있습니다:

* 정렬 안정성: 우선순위가 같은 두 개의 작업을 어떻게 원래 추가된 순서
  대로 반환합니까?

* 우선순위가 같고 작업에 기본 비교 순서가 없으면 (우선순위, 작업) 쌍에
  대한 튜플 비교가 성립하지 않습니다.

* 작업의 우선순위가 변경되면, 어떻게 힙의 새로운 위치로 옮깁니까?

* 또는 계류 중인 작업을 삭제해야 하면, 작업을 어떻게 찾고 큐에서 제거
  합니까?

처음 두 가지 과제에 대한 해결책은 항목을 우선순위, 항목 수 및 작업을
포함하는 3-요소 리스트로 저장하는 것입니다. 항목 수는 순위 결정자 역할
을 하므로 우선순위가 같은 두 작업이 추가된 순서대로 반환됩니다. 두 항
목 수가 같은 경우는 없어서, 튜플 비교는 두 작업을 직접 비교하려고 하지
않습니다.

비교할 수 없는 작업의 문제에 대한 또 다른 해결책은 작업 항목을 무시하
고 우선순위 필드만 비교하는 래퍼 클래스를 만드는 것입니다:

   from dataclasses import dataclass, field
   from typing import Any

   @dataclass(order=True)
   class PrioritizedItem:
       priority: int
       item: Any=field(compare=False)

나머지 과제는 계류 중인 작업을 찾고 우선순위를 변경하거나 완전히 제거
하는 것과 관련이 있습니다. 작업을 찾는 것은 큐에 있는 항목을 가리키는
딕셔너리를 사용해서 해결할 수 있습니다.

힙 구조 불변성을 깨뜨리기 때문에 항목을 제거하거나 우선순위를 변경하는
것은 더 어렵습니다. 따라서, 가능한 해결책은 항목을 제거된 것으로 표시
하고 우선순위가 수정된 새 항목을 추가하는 것입니다:

   pq = []                         # l힙에 배치된 항목의 리스트
   entry_finder = {}               # 작업에서 항목으로의 매핑
   REMOVED = '<removed-task>'      # 삭제된 작업을 위한 자리 표시기
   counter = itertools.count()     # 고유한 시퀀스 카운트

   def add_task(task, priority=0):
       '새 작업을 추가하거나 기존 작업의 우선순위를 갱신합니다'
       if task in entry_finder:
           remove_task(task)
       count = next(counter)
       entry = [priority, count, task]
       entry_finder[task] = entry
       heappush(pq, entry)

   def remove_task(task):
       '기존 작업을 REMOVED로 표시합니다.  발견되지 않으면 KeyError를 발생시킵니다.'
       entry = entry_finder.pop(task)
       entry[-1] = REMOVED

   def pop_task():
       '가장 낮은 우선순위 작업을 삭제하고 반환합니다. 비어있으면 KeyError를 발생시킵니다.
       while pq:
           priority, count, task = heappop(pq)
           if task is not REMOVED:
               del entry_finder[task]
               return task
       raise KeyError('pop from an empty priority queue')


이론
====

힙은 0부터 요소를 셀 때, 모든 *k*에 대해 "a[k] <= a[2*k+1]"와 "a[k] <=
a[2*k+2]"가 유지되는 배열입니다. 비교를 위해, 존재하지 않는 요소는 무
한인 것으로 간주합니다. 힙의 흥미로운 특성은 "a[0]"이 항상 가장 작은
요소라는 것입니다.

The strange invariant above is meant to be an efficient memory
representation for a tournament.  The numbers below are *k*, not
"a[k]":

   [그림: Example (min-heap) binary tree.][그림]

위의 트리에서, 각 셀 *k*는 "2*k+1"과 "2*k+2"위에 있습니다. 우리가 스포
츠에서 볼 수 있는 일반적인 이진 토너먼트에서, 각 셀은 아래에 있는 두
개의 셀의 승자가 되며, 트리 아래로 승자를 추적하여 모든 상대를 볼 수
있습니다. 그러나, 이러한 토너먼트의 많은 컴퓨터 응용에서 승자의 이력을
추적할 필요는 없습니다. 메모리 효율성을 높이기 위해, 승자가 승격될 때,
하위 수준에서 다른 것으로 대체하려고 시도합니다. 규칙은 셀과 셀 아래의
두 셀이 세 개의 다른 항목을 포함하지만, 위의 셀은 아래의 두 셀에 "이기
는" 것입니다.

이 힙 불변성이 항상 보호된다면, 인덱스 0은 분명히 최종 승자입니다. 이
것을 제거하고 "다음" 승자를 찾는 가장 간단한 알고리즘 적인 방법은 어떤
패자(위의 도표에서 셀 30이라고 합시다)를 0 위치로 옮기고, 불변성을 다
시 만족할 때까지 값을 교환하면서 이 새로운 0을 트리 아래로 침투시키는
것입니다. 이것은 트리의 총 항목 수에 대해 분명히 로그 함수적
(logarithmic)입니다. 모든 항목에 대해 반복하면, *O*(*n* log *n*) 정렬
을 얻게 됩니다.

이 정렬의 멋진 기능은 삽입된 항목이 추출한 마지막 0번째 요소보다 "더
나은" 항목이 아니라면, 정렬이 진행되는 동안 새 항목을 효율적으로 삽입
할 수 있다는 것입니다. 이는 트리가 들어오는 모든 이벤트를 담고, "승리"
조건이 가장 작은 예약 시간을 의미하는 시뮬레이션 문맥에서 특히 유용합
니다. 이벤트가 실행을 위해 다른 이벤트를 예약하면, 이들은 미래에 예약
되어서, 쉽게 힙에 들어갈 수 있습니다. 따라서, 힙은 스케줄러를 구현하기
에 좋은 구조입니다 (이것이 제가 MIDI 시퀀서에 사용한 것입니다 :-).

스케줄러를 구현하기 위한 다양한 구조가 광범위하게 연구되었으며, 힙은
합리적으로 빠르며, 속도가 거의 일정합니다, 최악의 경우는 평균 경우와
크게 다르지 않기 때문에 스케줄러에 좋습니다. 하지만, 최악의 경우는 끔
찍할 수 있습니다만, 전반적으로 더 효율적인 다른 표현이 있기는 합니다.

힙은 큰 디스크 정렬에도 매우 유용합니다. 여러분은 아마도 큰 정렬은 "런
(runs)"(크기가 일반적으로 CPU 메모리 크기와 관련된 사전 정렬된 시퀀스)
을 생성한 후에 이러한 런들에 대한 병합 패스가 따라옴을 의미하며, 이러
한 병합은 종종 매우 영리하게 조직됨을 알고 있을 겁니다 [1]. 초기 정렬
이 가능한 한 가장 긴 런을 생성하는 것이 매우 중요합니다. 토너먼트는 이
를 달성하기 위한 좋은 방법입니다. 토너먼트를 개최하는 데 사용할 수 있
는 모든 메모리를 사용하여 현재 런에 맞는 항목들을 교체하고 침투시키면,
무작위 입력을 위한 메모리 크기의 두 배인 런을 생성하게 되고, 적당히 정
렬된 입력에 대해서는 더 좋습니다.

더 나아가, 또한 디스크에 0번째 항목을 출력하고 현재 토너먼트에 맞지 않
는 입력을 받으면 (그 값이 마지막 출력값을 "이기기" 때문에), 힙에 넣을
수 없어서 힙의 크기가 줄어듭니다. 해제된 메모리는 두 번째 힙을 점진적
으로 구축하는데 즉시 영리하게 재사용될 수 있고, 두 번째 힙이 자라는 속
도는 첫 번째 힙이 줄어드는 것과 같습니다. 첫 번째 힙이 완전히 사라지면
, 힙을 전환하고 새 런을 시작합니다. 영리하고 매우 효과적입니다!

한마디로, 힙은 알아두어야 할 유용한 메모리 구조입니다. 저는 몇 가지 응
용 프로그램에서 사용하며, '힙' 모듈을 근처에 두는 것이 좋다고 생각합니
다. :-)

-[ 각주 ]-

[1] 요즘 최신 디스크 밸런싱 알고리즘은 영리하다기보다는 성가시며, 이는
    디스크의 탐색(seek) 기능으로 인한 결과입니다. 큰 테이프 드라이브와
    같이 탐색할 수 없는 장치에서는, 이야기가 상당히 달랐으며, 각 테이
    프 움직임이 가장 효과적일 수 있도록 (즉, 병합을 "진행하는데" 최대
    한 참여할 수 있도록) (일찌감치) 계획하기 위해 아주 영리해야 했습니
    다. 일부 테이프는 반대 방향으로 읽을 수도 있었으며, 이것은 되감기
    시간을 피하는 데 사용되기도 했습니다. 저를 믿으십시오, 진짜 훌륭한
    테이프 정렬은 장관이었습니다! 언제나, 정렬은 항상 위대한 예술이었
    습니다! :-)
