반응형
자료구조 ‘힙(heap)’이란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
- 완전 이진 트리 : 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
- 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 임으로 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
힙(heap)의 종류
- 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) >= key(자식 노드)
- 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) <= key(자식 노드)
이러한 성질 때문에 힙은 항상 느슨한 정렬상태(반정렬 상태)를 유지합니다.
힙(heap)의 구현
힙은 대체적으로 배열로 구현된다.
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
힙에서의 부모 노드와 자식 노드의 관계
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
힙(heap)의 삽입
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 가장 말단에 있는 노드의 자식 노드로 추가한다.
새로운 노드를 부모 노드들과 비교하면서 힙을 아래에서 위로 재구조화한다.
아래의 최대 힙(max heap)에 새로운 요소를 삽입해보자.
힙(heap)의 삭제
최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
삭제된 루트 노드 자리에는 가장 밑단 노드를 가져온다.
위에서 아래로 힙을 재구조화 한다.
아래의 최대 힙(max heap)에서 최댓값을 삭제해보자.
참조
반응형