Heap

Heap의 조건

• (Max heap인 경우)
• Maximum 값에 접근
• Maximum 값 삭제에
• push()에

• 위의 조건을 맞추기 위해서는 complete binary tree를 사용해야함.
  • 마지막 level의 node를 제외하고는 모두 2개의 child node가 있어야함.
• Complete binary tree를 사용하면 데이터 값 접근에 용이.

push()

• 새 데이터 node는 맨 끝에 추가하면 됨.
• 모든 node는 child node보다 더 큰 값을 가져야함.
  • 새로 데이터 node가 추가될 때, 부모 node와 값을 비교해서 필요하다면 swap 작업을 거침.
• Complete balanced tree의 높이는 최대 이므로 시간 복잡도는 이 됨.

pop()

• Root node 값만 삭제할 수 있음.
• Root node를 삭제하면 그 위치가 비어버림.
  • 그렇기 때문에, root node와 마지막 node의 값을 교환한 뒤, 마지막 node (기존의 root node)를 삭제함.
  • 그 후 새로 root node가 된 값을 child node와 비교해서 heap의 조건을 맞춤 (i.e. 모든 node는 child node보다 더 큰 값을 가져야함)

std::make_heap

• std::vector 또는 다른 배열들을 사용할 때 std::make_heap를 사용해서 곧바로 heap을 구현할 수 있음.
• 이는 std::priority_queue가 아닌 이미 std::vector 구조체를 사용할 때 유용함.