Python의 heapq 내장 모듈 소개에 대한 심층적인 이해

heapq는 python에 내장된 모듈입니다. 소스 코드는 Lib/heapq.py에 있습니다. 이 모듈은 힙 기반 우선 순위 지정 알고리즘을 제공합니다.

힙의 논리적 구조는 완전한 이진 트리이며, 이진 트리의 상위 노드 값은 해당 노드의 모든 하위 노드 값보다 작거나 같습니다. 이 구현은 heap[k] <= heap[2k+1] 및 heap[k] <= heap[2k+2](여기서 k는 index , 0부터 계산)를 사용할 수 있습니다. 힙의 경우 가장 작은 요소는 루트 요소 heap[0]입니다.

list를 통해 힙을 초기화하거나 api>Objectheapify를 통해 알려진 목록을 힙으로 변환할 수 있습니다 🎜>.

Heapq은 함수 메서드

heapq.heappush(heap, item)

heapq.heappop(heap)을 제공합니다. 루트 노드, 즉 힙에서 가장 작은 요소를 반환

heapq.heappushpop(heap, item): 힙에 항목 요소를 추가하고 힙에서 가장 작은 요소를 반환

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None): 열거 가능한 객체에서 가장 큰 n개의 값을 반환하고 결과 집합 목록을 반환합니다. 핵심은

heapq.nsmallest(n, iterable, key=None)의 결과 세트 작업입니다. 위와 동일하지만 반대입니다.

데모

1. heapq api를 통해 목록을 정렬

def heapsort(iterable):
    h = []

    for i in iterable:
        heapq.heappush(h, i)

    return [heapq.heappop(h) for i in range(len(h))]


s = [3, 5, 1, 2, 4, 6, 0, 1]
print(heapsort(s))

출력은 다음과 같습니다

 [0, 1, 1, 2, 3, 4, 5, 6]

2. 키를 통해 객체 목록에서 가장 작은 가격을 찾습니다. 항목

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(1, portfolio, key=lambda s: s['price'])
print(cheap)

은 다음과 같이 출력됩니다

[{'shares': 45, 'price': 16.35, 'name': 'YHOO'}]

extend

위에서 언급한 대로 heapq는 최소 힙의 구현이므로 리스트를 최소 힙으로 변환하는 방법을 heapq의 소스 코드를 기반으로 분석해 보겠습니다. Python의 API를 통해 (상위 노드의 키워드는 왼쪽 및 오른쪽 하위 노드보다 작습니다.)

는 다음 단계로 나눌 수 있습니다.

1. 자식 노드가 있는 경우 이 부모 노드 요소와 그 자식 노드를 하나의 단위로 취급합니다

2. 단위에서 두 자식 노드 중 더 작은 요소를 부모 노드와 교환합니다(판단할 필요 없음). 상위 노드와 가장 작은 하위 노드 간의 크기 관계) 이 단계를 통해 단위를 가장 작은 단위로 변경할 수 있습니다

3. 를 통해 더 작은 요소를 위로 밀어올릴 수 있습니다. > 루프

def heapilize_list(x):
    n = len(x)
    # 获取存在子节点的节点 index 列表，并对每个节点单元进行最小堆处理
    for i in reversed(range(n // 2)):
        raiseup_node(x, i)

def put_down_node(heap, startpos, pos):
    current_item = heap[pos]
    # 判断单元中最小子节点与父节点的大小
    while pos > startpos:
        parent_pos = (pos - 1) >> 1
        parent_item = heap[parent_pos]

        if current_item < parent_item:
            heap[pos] = parent_item
            pos = parent_pos
            continue
        break

    heap[pos] = current_item

def raiseup_node(heap, pos):
    heap_len = len(heap)
    start_pos = pos
    current_item = heap[pos]
    left_child_pos = pos * 2 + 1

    while left_child_pos < heap_len:
        right_child_pos = left_child_pos + 1
        # 将这个单元中的最小子节点元素与父节点元素进行位置调换
        if right_child_pos < heap_len and not heap[left_child_pos] < heap[right_child_pos]:
            left_child_pos = right_child_pos
        heap[pos] = heap[left_child_pos]
        pos = left_child_pos
        left_child_pos = pos * 2 + 1
    heap[pos] = current_item
    put_down_node(heap, start_pos, pos)


p = [4, 6, 2, 10, 1]
heapilize_list(p)
print(p)

출력은 다음과 같습니다

[1, 6, 2, 10, 4]

위 내용은 Python의 heapq 내장 모듈 소개에 대한 심층적인 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!