Python의 heapq 모듈 이해-파이썬 튜토리얼-php.cn

Python의 heapq 모듈 이해

Susan Sarandon

풀어 주다： 2024-09-19 18:16:31

원래의

624명이 탐색했습니다.

Understanding Python

Python에서 힙은 가장 작은(또는 가장 큰) 항목에 자주 빠르게 액세스해야 하는 요소 컬렉션을 효율적으로 관리하기 위한 강력한 도구입니다.

Python의 heapq 모듈은 우선순위 대기열 알고리즘이라고도 알려진 힙 대기열 알고리즘의 구현을 제공합니다.

이 가이드에서는 힙의 기본 사항과 heapq 모듈 사용 방법을 설명하고 몇 가지 실제 예제를 제공합니다.

힙이란 무엇입니까?

힙은 힙 속성을 충족하는 특별한 트리 기반 데이터 구조입니다.

최소 힙에서 특정 노드 I에 대해 I의 값은 해당 하위 노드의 값보다 작거나 같습니다. 따라서 가장 작은 요소는 항상 루트에 있습니다.
최대 힙에서 I의 값은 하위 요소의 값보다 크거나 같으므로 가장 큰 요소가 루트가 됩니다.

Python에서 heapq는 최소 힙을 구현합니다. 즉, 가장 작은 요소가 항상 힙의 루트에 있습니다.

왜 힙을 사용하는가?

힙은 필요할 때 특히 유용합니다.

최소 또는 최대 요소에 대한 빠른 액세스: 힙에서 가장 작거나 가장 큰 항목에 액세스하는 것은 O(1)입니다. 즉, 일정한 시간에 완료됩니다.
효율적인 삽입 및 삭제: 힙에 요소를 삽입하거나 가장 작은 요소를 제거하는 데는 O(log n) 시간이 소요되며 이는 정렬되지 않은 목록에 대한 작업보다 효율적입니다.

heapq 모듈

heapq 모듈은 일반 Python 목록에서 힙 작업을 수행하는 함수를 제공합니다.

사용 방법은 다음과 같습니다.

힙 만들기

힙을 생성하려면 빈 목록으로 시작하고 heapq.heappush() 함수를 사용하여 요소를 추가합니다.

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)

로그인 후 복사

이러한 작업 후 힙은 [5, 10, 20]이 되며 가장 작은 요소는 인덱스 0에 있습니다.

가장 작은 요소에 접근하기

힙[0]:
을 참조하면 제거하지 않고도 가장 작은 요소에 액세스할 수 있습니다.

smallest = heap[0]
print(smallest)  # Output: 5

로그인 후 복사

가장 작은 요소 팝핑

가장 작은 요소를 제거하고 반환하려면 heapq.heappop()을 사용하세요.

smallest = heapq.heappop(heap)
print(smallest)  # Output: 5
print(heap)  # Output: [10, 20]

로그인 후 복사

이 작업 후 힙이 자동으로 조정되고 다음으로 가장 작은 요소가 루트 위치를 차지합니다.

목록을 힙으로 변환

이미 요소 목록이 있는 경우 heapq.heapify()를 사용하여 이를 힙으로 변환할 수 있습니다.

numbers = [20, 1, 5, 12, 9]
heapq.heapify(numbers)
print(numbers)  # Output: [1, 9, 5, 20, 12]

로그인 후 복사

힙화 후 숫자는 [1, 9, 5, 12, 20]이 되어 힙 속성을 유지합니다.

여러 힙 병합

heapq.merge() 함수를 사용하면 여러 정렬된 입력을 단일 정렬 출력으로 병합할 수 있습니다.

heap1 = [1, 3, 5]
heap2 = [2, 4, 6]
merged = list(heapq.merge(heap1, heap2))
print(merged)  # Output: [1, 2, 3, 4, 5, 6]

로그인 후 복사

이렇게 하면 [1, 2, 3, 4, 5, 6]이 생성됩니다.

N개의 최대 또는 최소 요소 찾기

heapq.nlargest() 및 heapq.nsmallest()를 사용하여 데이터세트에서 가장 크거나 작은 n 요소를 찾을 수도 있습니다.

numbers = [20, 1, 5, 12, 9]
largest_three = heapq.nlargest(3, numbers)
smallest_three = heapq.nsmallest(3, numbers)
print(largest_three)  # Output: [20, 12, 9]
print(smallest_three)  # Output: [1, 5, 9]

로그인 후 복사

가장 큰_3은 [20, 12, 9]이고 가장 작은_3은 [1, 5, 9]입니다.

실제 예: 우선순위 대기열

힙의 일반적인 사용 사례 중 하나는 각 요소에 우선순위가 있고 우선순위가 가장 높은(가장 낮은 값) 요소가 먼저 제공되는 우선순위 대기열을 구현하는 것입니다.

import heapq


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


# Usage
pq = PriorityQueue()
pq.push('task1', 1)
pq.push('task2', 4)
pq.push('task3', 3)

print(pq.pop())  # Outputs 'task1'
print(pq.pop())  # Outputs 'task3'

로그인 후 복사

이 예에서 작업은 해당 우선순위와 함께 우선순위 대기열에 저장됩니다.

우선순위 값이 가장 낮은 작업이 항상 먼저 표시됩니다.