Heap

Heap

• 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조이다.
• 힙의 특징에는 최대힙일 경우 항상 부모가 자식보다 커야하고 형제간의 관계는 보지 않는다.
• 힙에서의 부모 노드와 자식 노드의 관계(index가 1부터 시작한다고 했을 때)
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

Min & Max Heap

• 바이너리 트리로 구현이 된다. 이것은 priority queue라고 볼 수 있다. 일정한 우선순위에 의해 나오게 되는 것을 의미한다.
• Max heap의 경우 부모 노드는 항상 자식들 보다 크게 된다.
• To parent: (index-1)/2
• Left child: 2*index + 1
• Right child: 2*index + 2
• 힙을 만드는데 필요한 time은 O(n)

import heapq

nums = [9,7,5,3,1]

heapq.heapfify(nums) => nums == [1,3,5,9,7]
heapq.heappop(nums) => output: 1
heapq.heappush(nums, 10)
heapq.heappushpop(nums, 11) => more efficiently peappush() then heappop()