[힙]

힙은 힙의 특성(최소 힙에서는 부무가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조다. 힙은 항상 균형을 유지하는 특징 때문에 다양한 분야에서 활용된다.

대표적으로 다익스트라에서 사용된다. 힙 덕분에 O(V^2)에서 O(ElogV)로 줄어든다. 힙정렬, 최소 신장 트리, 프림 알고리즘이나, 중앙 근사값에도 활용 될 수 있다.

[이진 힙]

자식이 둘인 힙, 대부분 이진 힙. 완전 이진 트리 형태인 이진 힙은 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용된다.

[힙구현]

(1) 뼈대 만들기.

class BinaryHeap(object):
	def __init__(self):
		self.items = [None]
 
	def __len__(self):
		return len(self.items) - 1

len(a)처럼 부르면 실제로는 a.len()이 불리는 매직함수.

0번째 배열은 미리 None을 삽입해둔다.

(2) 삽입.

def _percolate_up(self):
	i = len(self)
	parent = i // 2
	while parent > 0:
		if self.items[i] <self.items[parent]:
			self.items[parent], self.items[i] = self.items[i], self.items[parent]
		i = parent
		parent = i//2

def insert(self,k):
	self.items.append(k)
	self._percolate_up()

새로운 값이 들어오면, 가장 배열의 맨 끝에 들어오고 자기의 부모와 비교하며 위로 올라간다.

내부 함수라는 의미로 앞에 _를 붙였다. 시간 복잡도는 log(n)이다.

(3) 추출.

추출의 시간 복잡도도 O(log n)이다. 최소값을 제거하고 다시 힙의 특성을 유지해야기 때문이다.