[Python] Heap / Heap Queue(heapq)

힙(heap)배열의 

 

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)

 

• 힙 속성(property) : A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

 

• 최대 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
• Key(부모노드) >= Key(자식노드)

 

• 최소 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
• Key(부모노드) <= Key(자식노드)

힙(Heap) 구현

• 힙을 저장하는 자료구조는 배열
• 배열의 첫번째 인덱스 0은 사용되지 않음
• • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2
  • 힙에서의 부모 노드와 자식 노드의 관계
  •  

 

 

힙 함수 활용

• heapq.heappush(heap, item) : item을 heap에 추가
• heap.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어있는 경우  IndexError 호출
• heap.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환

코드

•