[면접대비] 힙(heap)

힙(heap)

• 이진트리에 속한다.
• 다음의 힙 조건(heap condition)중 하나를 만족시켜야 한다.
  • 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야 한다. 최대 힙.
  • 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 작아야 한다. 최소 힙.
• 트리는 완전해야 한다. 즉 빠진 노드 없이 완전히 채워져야 한다.
  • 바닥줄에는 빈 자리가 있ㅇ르 수 있다.
  • 빈 자리의 오른쪽으로는 어떤 노드도 없어야 한다.

힙의 시간복잡도

탐색: 각 노드를 모두 검사해야 하므로 검색 연산을 구현하지 않는다. 읽기 연산이 선택적으로 있을 수 있다.

삽입: 이진트리의 줄(line)은 모두 O(logN)개다. O(logN)

• 새 값을 포함하는 노드를 생성하고 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다.
• 삽입한 노드와 부모 노드를 비교한다.
• 새 노드가 부모 노드보다 크면 두 노드의 위치를 교환한다.
• 새 노드보다 큰 부모 노드를 만날 때까지 교환하여 새 노드를 힙 위로 올린다.
• 위로 올리는 과정은 노드를 위로 트리클링(trickling)한다고 표현한다.

삭제: 이진트리의 줄(line)은 모두 O(logN)개다. O(logN)

• 마지막 노드(=A)를 루트 노드 자리로 옮긴다.
• 루트 노드는 삭제된다. 큐의 동작 방식과 일치한다.
• 자식 노드 중 큰 노드보다 A가 작으면 큰 노드와 A를 교환한다.
• 루트 노드에는 큰 노드가 있고, 큰 노드의 자리에는 A가 있다.
• A보다 큰 자식이 없을 때까지 반복하여 자리르 교환한다.

* 마지막 노드를 찾는 방법

• 주로 배열을 사용해 힙을 구현한다.
• 루트 노드의 값 - 라인1 노드의 값 - 라인2 노드의 값의 순서대로 배열에 할당한다.
• 이 경우 가장 마지막 인덱스의 값이 항상 마지막 노드에 해당된다.
• 삽입, 삭제에서는 이 마지막 노드의 값을 사용하면 된다.