Emong's Factory

[자료구조][알고리즘] 히프(heap) - 최대 히프(max heap), 최소 히프(min heap)

히프(heap) 히프는 우선순위 큐(priority queue)를 구현하는 데 자주 사용된다. 우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다. 히프 또한, 완전 이진 트리(complete binary tree) 이다. 히프에는 최대 히프와 최소 히프가 있다. 최대(최소)트리[max(min) tree)]는 각 노드의 키 값이( 자식이 있다면) 그 자식의 키값보다 작지(크지) 않은 트리이다. 최대 히프(max heap)는 최대 트리이면서 완전 이진 트리이다. 최소 히프(min heap)는 최소 트리이면서 완전 이진 트리이다. 최대 히프에서의 삽입 새 노드에서 시작해서 루트 쪽으로 올라가는(bubblin..