힙 큐는 각 부모 노드가 자식 노드보다 작거나 같은 특수한 트리 구조입니다. pythin에서는 heapq 모듈을 사용하여 구현됩니다. 가중치가 높은 대기열 항목에 처리 우선 순위가 더 높은 우선 순위 대기열을 구현하는 것은 매우 유용합니다.
힙 생성
힙 큐는 heapq라는 파이썬의 내장 라이브러리를 사용하여 생성됩니다. 이 라이브러리는 힙 데이터 구조에 대한 다양한 연산을 수행하기 위한 관련 기능을 가지고 있습니다. 다음은 이러한 기능의 목록입니다.
- 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]