Python-힙
힙은 각 부모 노드가 자식 노드보다 작거나 같은 특수한 트리 구조입니다. 그런 다음 Min Heap이라고합니다. 각 부모 노드가 자식 노드보다 크거나 같으면 최대 힙이라고합니다. 가중치가 높은 대기열 항목이 처리에 더 많은 우선 순위를 부여하는 우선 순위 대기열을 구현하는 것은 매우 유용합니다. 힙에 대한 자세한 내용은 여기 웹 사이트에서 확인할 수 있습니다. 헤드 데이터 구조를 처음 사용하는 경우 먼저 연구하십시오. 이 장에서는 파이썬을 사용한 힙 데이터 구조의 구현을 볼 것입니다.
힙 생성
힙은 heapq라는 Python의 내장 라이브러리를 사용하여 생성됩니다. 이 라이브러리에는 힙 데이터 구조에 대한 다양한 작업을 수행하는 관련 기능이 있습니다. 다음은 이러한 기능의 목록입니다.
- heapify-이 함수는 일반 목록을 힙으로 변환합니다. 결과 힙에서 가장 작은 요소가 인덱스 위치 0으로 푸시됩니다. 그러나 나머지 데이터 요소가 반드시 정렬되는 것은 아닙니다.
- heappush –이 함수는 현재 힙을 변경하지 않고 힙에 요소를 추가합니다.
- heappop-이 함수는 힙에서 가장 작은 데이터 요소를 반환합니다.
- heapreplace –이 함수는 가장 작은 데이터 요소를 함수에 제공된 새 값으로 바꿉니다.
힙 생성
힙은 단순히 heapify 함수가있는 요소 목록을 사용하여 생성됩니다. 아래 예에서 요소 목록을 제공하고 heapify 함수는 가장 작은 요소를 첫 번째 위치로 가져 오는 요소를 재정렬합니다.
import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.
[1, 3, 5, 78, 21, 45]힙에 삽입
데이터 요소를 힙에 삽입하면 항상 마지막 인덱스에 요소가 추가됩니다. 그러나 heapify 함수를 다시 적용하여 값이 가장 작은 경우에만 새로 추가 된 요소를 첫 번째 인덱스로 가져올 수 있습니다. 아래 예에서는 숫자 8을 삽입합니다.
import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.
[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]힙에서 제거
이 함수를 사용하여 첫 번째 인덱스에서 요소를 제거 할 수 있습니다. 아래 예에서 함수는 항상 인덱스 위치 1의 요소를 제거합니다.
import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Remove element from the heap
heapq.heappop(H)
print(H)위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.
[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]힙에서 바꾸기
heapreplace 함수는 항상 힙의 가장 작은 요소를 제거하고 순서에 따라 고정되지 않은 위치에 새로 들어오는 요소를 삽입합니다.
import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Replace an element
heapq.heapreplace(H,6)
print(H)[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]