개요

매 분마다 비행기가 이착륙하는 분주한 공항을 상상해 보십시오. 항공 교통 관제사가 긴급성을 기준으로 항공편의 우선순위를 정하는 것처럼 힙은 특정 기준에 따라 데이터를 관리하고 처리하는 데 도움이 되므로 가장 "긴급"하거나 "중요한" 데이터가 항상 최상위에서 액세스할 수 있도록 보장합니다.

이 가이드에서는 처음부터 힙을 이해하는 여정을 시작하겠습니다. 힙이 무엇인지, 그리고 그 고유한 속성을 이해하는 것부터 시작하겠습니다. 거기에서 우리는 파이썬의 힙 구현에 대해 자세히 알아볼 것입니다. heapq 모듈을 살펴보고 풍부한 기능 세트를 살펴보세요. 따라서 가장 높은(또는 가장 낮은) 우선순위 요소가 자주 필요한 동적 데이터 세트를 효율적으로 관리하는 방법에 대해 궁금한 적이 있다면 좋은 해결책이 될 것입니다.

힙이란 무엇입니까?

힙 사용법을 알아보기 전에 가장 먼저 이해하고 싶은 것은 힙이 뭐야?. 힙은 데이터 구조의 세계에서 트리 기반의 강자로 두드러지며, 특히 다음과 같은 작업에 능숙합니다. 질서와 계층 유지. 훈련받지 않은 사람의 눈에는 이진 트리와 비슷할 수 있지만 구조와 관리 규칙의 미묘한 차이로 인해 이 트리가 뚜렷이 구분됩니다.

힙을 정의하는 특징 중 하나는 힙의 성격입니다. 완전한 이진 트리. 이는 마지막 레벨을 제외하고 트리의 모든 레벨이 완전히 채워졌음을 의미합니다. 이 마지막 수준 내에서 노드는 왼쪽에서 오른쪽으로 채워집니다. 이러한 구조를 사용하면 배열 또는 목록을 사용하여 힙을 효율적으로 표현하고 조작할 수 있으며, 배열의 각 요소 위치는 트리에서의 위치를 ​​미러링합니다.

그러나 힙의 진정한 본질은 힙에 있습니다. 주문하기. 에 최대 힙, 지정된 노드의 값은 해당 하위 노드의 값보다 크거나 같으며 가장 큰 요소가 루트에 바로 배치됩니다. 반면에, 최소 힙 반대 원칙에 따라 작동합니다. 모든 노드의 값은 자식 값보다 작거나 같으며 가장 작은 요소가 루트에 위치하도록 보장합니다.

진행하면서 이러한 힙의 고유한 속성이 효율적인 작업을 가능하게 하는 방법과 Python의 heapq 모듈은 코딩 작업에 힙을 원활하게 통합합니다.

힙의 특성 및 속성

고유한 구조와 순서 원칙을 갖춘 힙은 다양한 계산 시나리오에서 매우 귀중한 고유한 특성과 속성 집합을 제공합니다.

무엇보다도 힙은 다음과 같습니다. 본질적으로 효율적. 트리 기반 구조, 특히 완전한 이진 트리 형식은 우선 순위 요소(최대 또는 최소)의 삽입 및 추출과 같은 작업을 일반적으로 로그 시간 내에 수행할 수 있도록 보장합니다. O (로그 n). 이러한 효율성은 우선 순위 요소에 자주 액세스해야 하는 알고리즘 및 애플리케이션에 도움이 됩니다.

힙의 또 다른 주목할만한 속성은 메모리 효율. 힙은 자식 노드나 부모 노드에 대한 명시적인 포인터 없이 배열이나 목록을 사용하여 표현될 수 있으므로 공간이 절약됩니다. 배열의 각 요소 위치는 트리에서의 위치와 일치하므로 예측 가능하고 간단한 탐색 및 조작이 가능합니다.

최대 힙이든 최소 힙이든 힙의 순서 속성은 다음을 보장합니다. 루트는 항상 가장 높은 우선순위의 요소를 보유합니다.. 이러한 일관된 순서 덕분에 전체 구조를 검색할 필요 없이 최우선 순위 요소에 빠르게 액세스할 수 있습니다.

게다가 힙은 다양한. 이진 힙(각 부모가 최대 XNUMX개의 자식을 가짐)이 가장 일반적이지만 힙은 두 개 이상의 자식을 갖도록 일반화될 수 있습니다. d-ary 힙. 이러한 유연성을 통해 특정 사용 사례 및 성능 요구 사항에 따라 세부 조정이 가능합니다.

마지막으로 힙은 자체 조정. 요소가 추가되거나 제거될 때마다 구조는 속성을 유지하기 위해 자체적으로 재배열됩니다. 이러한 동적 균형 조정을 통해 힙은 항상 핵심 작업에 맞게 최적화된 상태로 유지됩니다.

Python의 구현과 실제 응용 프로그램을 더 깊이 파고들면 힙의 진정한 잠재력이 우리 앞에 펼쳐질 것입니다.

힙의 유형

모든 힙이 동일하게 생성되는 것은 아닙니다. 순서 및 구조적 속성에 따라 힙은 다양한 유형으로 분류될 수 있으며 각 유형에는 고유한 응용 프로그램 및 장점이 있습니다. 두 가지 주요 카테고리는 다음과 같습니다. 최대 힙 및 최소 힙.

A의 가장 차별화된 특징은 최대 힙 주어진 노드의 값이 그 자식 노드의 값보다 크거나 같다는 것입니다. 이렇게 하면 힙에서 가장 큰 요소가 항상 루트에 위치하게 됩니다. 이러한 구조는 특정 우선순위 대기열 구현에서와 같이 최대 요소에 자주 액세스해야 할 때 특히 유용합니다.

최대 힙에 대응하는 것, 최소 힙 특정 노드의 값이 해당 하위 노드의 값보다 작거나 같은지 확인합니다. 이렇게 하면 힙의 가장 작은 요소가 루트에 배치됩니다. 최소 힙은 실시간 데이터 처리를 처리하는 알고리즘과 같이 가장 작은 요소가 가장 중요한 시나리오에서 매우 중요합니다.

이러한 기본 범주 외에도 힙은 분기 요소에 따라 구별될 수도 있습니다.

바이너리 힙이 가장 일반적이지만 각 상위에는 최대 XNUMX개의 하위가 있지만 힙의 개념은 XNUMX개 이상의 하위가 있는 노드로 확장될 수 있습니다. 안에 d-ary 힙, 각 노드는 최대 d 어린이들. 이 변형은 특정 작업 속도를 높이기 위해 트리 높이를 줄이는 것과 같은 특정 시나리오에 최적화될 수 있습니다.

이항 힙 재귀적으로 정의되는 이항 트리의 집합입니다. 이항 힙은 우선순위 대기열 구현에 사용되며 효율적인 병합 작업을 제공합니다.

유명한 피보나치 수열의 이름을 따서 명명되었습니다. 피보나치 힙 이진 또는 이항 힙에 비해 많은 작업에 대해 더 나은 상각 실행 시간을 제공합니다. 특히 네트워크 최적화 알고리즘에 유용합니다.

Python의 힙 구현 – 힙큐 모듈

Python은 힙 작업을 위한 내장 모듈을 제공합니다. heapq 기준 치수. 이 모듈은 개발자가 목록을 힙으로 변환하고 사용자 지정 구현 없이 다양한 힙 작업을 수행할 수 있도록 하는 힙 관련 기능 모음을 제공합니다. 이 모듈의 미묘한 차이와 이 모듈이 어떻게 힙의 강력한 기능을 제공하는지 살펴보겠습니다.

XNUMXD덴탈의 heapq 모듈은 고유한 힙 데이터 유형을 제공하지 않습니다. 대신, 일반 Python 목록에서 작동하는 함수를 제공하여 이를 다음과 같이 변환하고 처리합니다. 바이너리 힙.

이 접근 방식은 메모리 효율적이며 Python의 기존 데이터 구조와 원활하게 통합됩니다.

즉, 힙은 목록으로 표현됩니다. in heapq. 이 표현의 장점은 단순성입니다. XNUMX부터 시작하는 목록 인덱스 시스템은 암시적 이진 트리 역할을 합니다. 위치에 있는 특정 요소에 대해 i, 그것은:

• 왼쪽 자식이 위치에 있음 2*i + 1
• 오른쪽 자식이 위치에 있음 2*i + 2
• 상위 노드가 위치에 있습니다. (i-1)//2

이 암시적 구조를 통해 별도의 노드 기반 이진 트리 표현이 필요하지 않으므로 작업이 간단해지고 메모리 사용량이 최소화됩니다.

다음 사항에 유의하는 것이 중요합니다. heapq 모듈 기본적으로 최소 힙을 생성합니다.. 이는 가장 작은 요소가 항상 루트(또는 목록의 첫 번째 위치)에 있음을 의미합니다. 최대 힙이 필요한 경우 요소에 다음을 곱하여 순서를 뒤집어야 합니다. -1 또는 사용자 정의 비교 기능을 사용하십시오.

파이썬 heapq 모듈은 개발자가 목록에 대해 다양한 힙 작업을 수행할 수 있도록 하는 일련의 기능을 제공합니다.

다음 섹션에서는 이러한 기본 작업 각각에 대해 자세히 알아보고 해당 메커니즘과 사용 사례를 살펴보겠습니다.

목록을 힙으로 변환하는 방법

XNUMXD덴탈의 heapify() 함수는 많은 힙 관련 작업의 시작점입니다. 이터러블(일반적으로 목록)을 사용하고 최소 힙의 속성을 충족하기 위해 해당 요소를 제자리에 다시 정렬합니다.

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

유효한 최소 힙을 나타내는 재정렬된 목록이 출력됩니다.

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

힙에 요소를 추가하는 방법

XNUMXD덴탈의 heappush() 함수를 사용하면 힙의 속성을 유지하면서 힙에 새 요소를 삽입할 수 있습니다.

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

코드를 실행하면 최소 힙 속성을 유지하는 요소 목록이 제공됩니다.

[3, 5, 7]

힙에서 가장 작은 요소를 제거하고 반환하는 방법

XNUMXD덴탈의 heappop() 함수는 힙(최소 힙의 루트)에서 가장 작은 요소를 추출하고 반환합니다. 제거 후에는 목록이 유효한 힙으로 유지되는지 확인합니다.

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

그러면 가장 작은 요소와 나머지 목록이 출력됩니다.

1
[3, 7, 5, 9]

여기 1 에서 가장 작은 원소이다. heap, 나머지 목록은 제거한 후에도 힙 속성을 유지했습니다. 1.

새 항목을 푸시하고 가장 작은 항목을 팝하는 방법

XNUMXD덴탈의 heappushpop() 함수는 새 항목을 힙에 푸시한 다음 힙에서 가장 작은 항목을 팝하고 반환하는 결합된 작업입니다.

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

그러면 출력됩니다. 3, 가장 작은 요소를 선택하고 새 요소를 인쇄합니다. heap 이제 포함된 목록 4 힙 속성을 유지하면서 다음을 수행합니다.

3
[4, 5, 7, 9]

가장 작은 항목을 교체하고 새 항목을 푸시하는 방법

XNUMXD덴탈의 heapreplace() 함수는 하나의 효율적인 작업으로 가장 작은 요소를 팝하고 새 요소를 힙에 푸시합니다.

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

이것은 인쇄 1, 가장 작은 요소, 목록에는 이제 4가 포함되고 힙 속성이 유지됩니다.

1
[4, 5, 7, 9]

Python의 힙에서 여러 극단 찾기

nlargest(n, iterable[, key]) 및 nsmallest(n, iterable[, key]) 함수는 반복 가능 항목에서 가장 크거나 가장 작은 여러 요소를 검색하도록 설계되었습니다. 소수의 극값만 필요한 경우 전체 반복 가능 항목을 정렬하는 것보다 더 효율적일 수 있습니다. 예를 들어, 다음 목록이 있고 목록에서 가장 작은 값 XNUMX개와 가장 큰 값 XNUMX개를 찾으려고 한다고 가정해 보겠습니다.

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

여기 nlargest() 및 nsmallest() 다음과 같은 기능이 유용할 수 있습니다.

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

그러면 두 개의 목록이 제공됩니다. 하나는 세 개의 가장 큰 값을 포함하고 다른 하나는 세 개의 가장 작은 값을 포함합니다. data 명부:

[9, 6, 5]
[1, 1, 2]

사용자 정의 힙을 구축하는 방법

반면 파이썬은 heapq 모듈은 힙 작업을 위한 강력한 도구 세트를 제공하지만 기본 최소 힙 동작이 충분하지 않을 수 있는 시나리오가 있습니다. 최대 힙을 구현하려는 경우 또는 사용자 정의 비교 기능을 기반으로 작동하는 힙이 필요한 경우 사용자 정의 힙을 구축하는 것이 답이 될 수 있습니다. 특정 요구 사항에 맞게 힙을 조정하는 방법을 살펴보겠습니다.

다음을 사용하여 최대 힙 구현 heapq

기본적으로, heapq 생성 최소 힙. 그러나 간단한 트릭을 사용하여 최대 힙을 구현할 수 있습니다. 아이디어는 요소에 다음을 곱하여 요소의 순서를 바꾸는 것입니다. -1 힙에 추가하기 전에:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

이 접근 방식을 사용하면 (절대값 측면에서) 가장 큰 숫자가 가장 작아집니다. heapq 최대 힙 구조를 유지하는 기능입니다.

사용자 정의 비교 함수가 있는 힙

때로는 요소의 자연스러운 순서에 따라 비교하지 않는 힙이 필요할 수도 있습니다. 예를 들어, 복잡한 개체로 작업하거나 특정 정렬 기준이 있는 경우 사용자 정의 비교 기능이 필수적입니다.

이를 달성하려면 비교 연산자를 재정의하는 도우미 클래스에 요소를 래핑할 수 있습니다.

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

이 설정을 사용하면 사용자 정의 비교기 함수를 정의하고 이를 힙과 함께 사용할 수 있습니다.

결론

힙은 많은 작업에 대해 예측 가능한 성능을 제공하므로 우선순위 기반 작업에 안정적인 선택이 됩니다. 그러나 현재 애플리케이션의 특정 요구 사항과 특성을 고려하는 것이 중요합니다. 경우에 따라 힙 구현을 조정하거나 대체 데이터 구조를 선택하면 실제 성능이 향상될 수도 있습니다.

지금까지 살펴본 것처럼 힙은 단순한 데이터 구조 그 이상입니다. 이는 효율성, 구조 및 적응성의 융합을 나타냅니다. 기본 속성부터 Python의 구현까지 heapq 모듈에서 힙은 수많은 계산 문제, 특히 우선순위를 중심으로 한 문제에 대한 강력한 솔루션을 제공합니다.

• SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
• PlatoData.Network 수직 생성 Ai. 자신에게 권한을 부여하십시오. 여기에서 액세스하십시오.
• PlatoAiStream. 웹3 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
• 플라톤ESG. 탄소, 클린테크, 에너지, 환경, 태양광, 폐기물 관리. 여기에서 액세스하십시오.
• PlatoHealth. 생명 공학 및 임상 시험 인텔리전스. 여기에서 액세스하십시오.
• 출처: https://stackabuse.com/guide-to-heaps-in-python/