[자료구조] 힙(Heap)

■ Heap

• 힙(heap)은 완전 이진 트리(Completable Binary Tree) 를 기본으로 한 자료구조 (tree-based structure)
• 시간복잡도 : O(logn)
• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
• 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

 

※ 힙의 특징

• 일반적으로 배열을 사용하여 구현한다.배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. (우선순위큐 구현시 사용함)
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

 

※ 힙의 종류

▷ 최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)
• 최대값을 찾는데 소요되는 연산의 시간복잡도가 O(1) 이다.
• 완전 이진 트리(Completable Binary Tree) 이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.
• 즉 random access 가 가능하다.

▷ 최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)
• 키값의 대소관계는 부모-자식 간에만 성립하고, 형제 간에는 성립하지 않는다.
• 최소값을 찾는데 소요되는 연산의 시간복잡도가 O(1) 이다.

 

 

※ 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열 이다.
• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  
  • 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 힙에서의 부모 노드와 자식 노드의 관계
  
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2
    
    

 

▶ 삽입 (max heap 기준)

1. 힙의 가장 마지막 원소에 원하는 값을 삽입한다.
2. 부모가 삽입 원소보다 작다면(Max_Heap기준) 부모와 자식의 값을 교환한다.
3. 2번에서 부모가 없거나, 부모가 자식보다 클 경우에 종료

 

▶ 삭제 (max heap 기준)

1. 루트노드를 삭제하고 힙의 마지막 노드를 루트로 가져온다.
2. 가져온 루트와 자식노드를 비교하고 가져온 노드가 작을 경우 자식과 위치 변경
3. 자식 노드가 더이상 없거나, 자식보다 클 경우 종료