Sean :: Dev

Heap (힙) Max Heap / Min Heap Parent Node가 Child Node보다 항상 크거나(작거나) 같은 Complete Binary Tree (완전이진트리) (자식노드끼리는 상관없음) (항상 root가 max/min이므로 최대-최소값을 찾기 편하다) 시간 복잡도 : O(logn) (힙의 삽입-삭제는 최악의 경우, 최하단노드~최상단노드까지 swap이 필요하다) 삽입&삭제 시에도 '완전이진트리'형태를 유지해야한다. 삽입 : 마지막 노드의 다음자리를 확장하고 임시로 저장후, 부모노드와 비교해가며 swap한다. 삭제 : 항상 root를 삭제해 반환한다. 마지막 노드를 root자리에 임시로 저장후 삭제하고, root에 있는 값을 자식들과 비교해가며 적당한 자리까지 swap한다...