이진 트리의 한 종류.

1. root노드가 언제나 최소/최대값을 가짐
2. 완전 이진 트리여야 함

최대 힙

부모 노드가 자식 노드보다 큰 값을 가져야 함

O($logn$)

-노드 번호 m (1부터 시작한다 가정) -왼쪽 자식번호 : 2 * m -오른쪽 자식번호 : 2 * m + 1 -부모노드 번호 : m // 2

• 구현방법

활용 : 우선순위 큐, 힙 정렬[O($nlogn$)]

def heapsort(unsorted):
	H = MaxHeap()
	for item in unsorted:
		H.insert(item)
	sorted = []
	d = H.remove()
	while d:
		sorted.append(d)
		d = H.remove()
	return sorted