Python 의 hepq 모듈 원본 상세 분석

시작 하 다
이것 은 상당히 실 용적 인 내장 모듈 이지 만 많은 사람들 이 그의 존 재 를 모른다―필자 도 오늘 우연히 보 았 다.아...그럼 에 도 불구 하고 이 모듈 이 좋 은 사실 을 바 꿀 수 없다.
hepq 모듈 은 Python 목록 에 적용 되 는 최소 정렬 알고리즘 을 실현 합 니 다.

더 미 는 나무 모양 의 데이터 구조 로 그 중의 하위 노드 는 모두 부모 와 순서 관 계 를 가진다.정렬 된 트 리 는 이 진 트 리 가 가득 하기 때문에 목록 으로 트 리 의 구 조 를 표시 할 수 있 습 니 다.요소 N 의 하위 요 소 는 2N+1 과 2N+2 의 위치 에 있 습 니 다(0 에서 시작 하 는 색인 에 대해).
본 논문 의 내용 은 세 부분 으로 나 뉘 는데 첫 번 째 부분 은 hepq 모듈 의 사용 을 간단하게 소개 합 니 다.두 번 째 부분 회고 더미 정렬 알고리즘;세 번 째 부분 은 hepq 의 실현 을 분석한다.
hepq 사용
더 미 를 만 드 는 데 는 두 가지 기본 적 인 방법 이 있 습 니 다.heppush()와 hepify(),더 미 를 꺼 내 서 heppop()을 사용 합 니 다.
heppush()는 기 존 더미 에 요 소 를 추가 하 는 데 사 용 됩 니 다.보통 빈 목록 부터 구축 합 니 다.

import heapq

data = [97, 38, 27, 50, 76, 65, 49, 13]
heap = []

for n in data:
 heapq.heappush(heap, n)

print('pop:', heapq.heappop(heap)) # pop: 13
print(heap) # [27, 50, 38, 97, 76, 65, 49]

데이터 가 목록 에 있 으 면 hepify()를 사용 하여 정렬 합 니 다.

import heapq

data = [97, 38, 27, 50, 76, 65, 49, 13]

heapq.heapify(data)

print('pop:', heapq.heappop(data)) # pop: 13
print(data) # [27, 38, 49, 50, 76, 65, 97]

회고 더미 정렬 알고리즘
쌓 기 정렬 알고리즘 의 기본 사상 은 무질서 한 서열 을 쌓 아서 키워드 가 가장 작 거나 가장 큰 기록 을 얻 는 것 이다.출력 더미 꼭대기 의 최소(큰)값 을 출력 한 후 남 은 n-1 개의 요 소 를 다시 쌓 으 면 n 개의 요소 의 작은 값 을 얻 을 수 있 습 니 다.반복 적 으로 실행 하면 질서 있 는 서열 을 얻 을 수 있 습 니 다.이것 이 바로 정렬 과정 입 니 다.
쌓 기 정렬 은 두 가지 문 제 를 해결 해 야 합 니 다.

어떻게 무질서 한 서열 로 쌓 입 니까?

어떻게 지붕 요 소 를 출력 한 후에 나머지 요 소 를 조정 하여 새로운 더미 로 만 듭 니까?

새로운 요 소 를 추가 하고 더 미 를 어떻게 조정 합 니까?

두 번 째 문제 의 해결 방법 부터 살 펴 보 자.사용 하 는 방법 은'선별'이 라 고 합 니 다.출력 더미 의 맨 위 요 소 를 출력 한 후에 더미 의 마지막 요 소 를 대체 합 니 다.그 다음 에 뿌리 결산 점 수 치 를 왼쪽,오른쪽 나무의 뿌리 결산 점 수 치 를 비교 하고 그 중의 작은 사람과 교환 합 니 다.상기 조작 을 반복 하면 잎 이 맺 힐 때 까지 새로운 더 미 를 얻 을 수 있 는데 이것 은 쌓 인 지붕 에서 잎 까지 의 조정 과정 을'선별'이 라 고 부른다.

위의 그림 에서 보 듯 이 쌓 인 지붕 13 이 출력 되면 쌓 인 끝의 97 을 쌓 은 지붕 으로 대체 한 다음 에 쌓 인 지붕 과 그의 하위 노드 38 과 27 중의 작은 자 를 교환 합 니 다.요소 97 은 새로운 위치 에서 그의 하위 노드 65 와 49 의 작은 사람과 교환 합 니 다.원소 97 이 잎 노드 가 될 때 까지 새로운 더 미 를 얻 었 다.이 과정 도 침하 라 고 한다.
더미 의 위 치 를 pos 요소 로 가 라 앉 히 는 것 은 다음 과 같 습 니 다.

def heapdown(heap, pos):
 endpos = len(heap)
 while pos < endpos:
 lchild = 2 * pos + 1
 rchild = 2 * pos + 2
 if lchild >= endpos: #   pos      ，    
  break
 childpos = lchild #             
 if rchild < endpos and heap[childpos] > heap[rchild]:
  childpos = rchild

 if heap[pos] < heap[childpos]: #           ，    
  break
 heap[pos], heap[childpos] = heap[childpos], heap[pos] #   
 pos = childpos

세 번 째 문 제 를 어떻게 해결 하 는 지 살 펴 보 자.새로운 요소 와 더 미 를 어떻게 조정 하 는 지?이 방법 은 가라앉 은 것 과 반대로 먼저 새로운 요 소 를 목록 의 마지막 에 놓 은 다음 에 새로운 요 소 를 부모 노드 와 비교 하고 부모 노드 보다 작 으 면 부모 노드 와 교환 합 니 다.부모 노드 보다 크 거나 루트 노드 까지 반복 합 니 다.이 과정 은 원 소 를 바닥 에서 계속 상승 시 키 고 아래 에서 위로 쌓 아 올 리 는 순 서 를 상부 라 고 한다.
위 치 를 pos 로 올 리 는 코드 는:

def heapup(heap, startpos, pos): #        ，startpos    0
 while pos > startpos:
 parentpos = (pos - 1) // 2
 if heap[pos] < heap[parentpos]:
  heap[pos], heap[parentpos] = heap[parentpos], heap[pos]
  pos = parentpos
 else:
  break

첫 번 째 문제:어떻게 무질서 한 서열 로 쌓 입 니까?무질서 한 서열 의 n/2 번 째 요소(즉,이 무질서 한 서열 에 대응 하 는 완전 이 진 트 리 의 마지막 비 터미널 노드)부터 첫 번 째 요소 가 멈 출 때 까지 순서대로 내 려 갑 니 다.

for i in reversed(range(len(data) // 2)):
 heapdown(data, i)

hepq 소스 코드 분석
더미 에 새 요 소 를 추가 하 는 heppush()함수:

def heappush(heap, item):
 """Push item onto heap, maintaining the heap invariant."""
 heap.append(item)
 _siftdown(heap, 0, len(heap)-1)

대상 요 소 를 목록 의 마지막 에 놓 고 올 립 니 다.다운 이 라 고 명명 되 었 음 에 도 불구 하고 이 과정 은 떠 오 르 는 과정 이 었 습 니 다.이 이름 은 저 를 곤 혹 스 럽 게 했 습 니 다.나중에 야 저 는 요소 의 색인 이 계속 줄 어 들 기 때문에 다운 이 라 고 명명 한 것 을 알 게 되 었 습 니 다.가라앉 는 과정 도 up 이 라 고 명명 되 었 다.

def _siftdown(heap, startpos, pos):
 newitem = heap[pos]
 # Follow the path to the root, moving parents down until finding a place
 # newitem fits.
 while pos > startpos:
  parentpos = (pos - 1) >> 1
  parent = heap[parentpos]
  if newitem < parent:
   heap[pos] = parent
   pos = parentpos
   continue
  break
 heap[pos] = newitem

마찬가지 로 new item 을 통 해 부모 노드 와 계속 비교 합 니 다.다른 것 은 여기 서 요소 교환 과정 이 부족 하고 새로운 요소 가 마지막 에 있 는 위치 pos 를 계산 하여 할당 하 는 것 입 니 다.분명히 이것 은 최 적 화 된 코드 로 끊임없이 원 소 를 교환 하 는 불필요 한 과정 을 줄 였 다.
출력 더미 요소 의 함수 heppop()를 다시 보 겠 습 니 다.

def heappop(heap):
 """Pop the smallest item off the heap, maintaining the heap invariant."""
 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
 if heap:
  returnitem = heap[0]
  heap[0] = lastelt
  _siftup(heap, 0)
  return returnitem
 return lastelt

힙 합.pop()을 통 해 목록 의 마지막 요 소 를 얻 은 다음 힙[0]=lastelt 로 교체 하고 가 라 앉 히 기:

def _siftup(heap, pos):
 endpos = len(heap)
 startpos = pos
 newitem = heap[pos]
 # Bubble up the smaller child until hitting a leaf.
 childpos = 2*pos + 1 #    ，       
 while childpos < endpos:
  # Set childpos to index of smaller child.
  rightpos = childpos + 1 #    
  if rightpos < endpos and not heap[childpos] < heap[rightpos]:
   childpos = rightpos #         ，        
  # Move the smaller child up.
  heap[pos] = heap[childpos]
  pos = childpos
  childpos = 2*pos + 1
 # The leaf at pos is empty now. Put newitem there, and bubble it up
 # to its final resting place (by sifting its parents down).
 heap[pos] = newitem
 _siftdown(heap, startpos, pos)

이 코드 는 가라앉 을 요 소 를 새로운 요소 new item 으로 보고 현재 위치 pos 를 빈 위치 로 보고 하위 노드 의 작은 사람 으로 대체 합 니 다.반복 하면 마지막 으로 잎 노드 에 위 치 를 남 깁 니 다.이 위 치 는 new item 에 넣 고 새로운 요 소 를 올 립 니 다.
무질서 한 수열 을 다시 배열 하 는 hepify()함수 다시 보기:

def heapify(x):
 """Transform list into a heap, in-place, in O(len(x)) time."""
 n = len(x)
 for i in reversed(range(n//2)):
  _siftup(x, i)

이 부분 은 이론 적 인 것 과 일치 하고 마지막 비 엽 노드(n//2)에서 뿌리 노드 까지 침하 한다.
총결산
정렬 결합 도 를 쌓 아서 이해 하 는 것 이 비교적 이해 하기 쉽다.이 데이터 구 조 는 항상 우선 대기 열(표준 라 이브 러 리 Queue 의 우선 대기 열 은 더미)에 사 용 됩 니 다.hepq 모듈 에는 또 다른 hepreplace,heppushpop 등 이 대체적으로 유사 하 다.
자,이상 이 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.