[자료구조] Heap

Heap

• Heap tree or Heap이라고 불린다.
• 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진트리를 말한다.
• 우선순위 Queue를 위하여 만들어진 자료구조이다.
• 힙은 일종의 반 정렬 상태(느슨한 정렬 상태)를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다)
• 힙은 계산 편의를 위해 인덱스를 1부터 사용한다 (parent: x, left: 2x, right: 2x+1)

힙의 데이터 삽입

여기서 규칙이란 최소힙, 최대힙의 규칙을 의미한다.

1. 리프 노드에 삽입할 노드를 삽입한다.
2. 해당 노드와 부모 노드를 서로 비교한다.
3. "규칙"에 맞으면 그대로 두고, 그렇지 않으면 부모 노드와 교환한다.
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

최소힙의 삽입과정

힙의 데이터 참조(삭제)

루트 노드만을 제거할 수 있으며, 다음과 같은 과정이 일어난다.

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드과 비교한다.
4. 규칙을 만족하면 그대로 두고, 그렇지 않으면 자식노드와 교환한다.

최소힙의 참조 과정

이진 트리와의 차이점

이진 트탐색트리는 탐색을 쉽게 하기 위해 왼쪽이 더 작고 오른쪽이 큰 값으로 꼭 구성이 되어야 하지만, Heap은 그렇지 않다.

시간복잡도

• 참조(최대 또는 최소값을 참조) : O(1)
• 탐색 : O(n)
• 삽입 / 삭제 : O(logn)