힙 (Heap)

힙 (Heap)

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

힙은 일종의 반정렬 상태를 유지 (부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리)
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

힙(heap)의 구현 

힙을 저장하는 표준적인 자료구조는 배열 이다. 
구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

힙에서의 부모 노드와 자식 노드의 관계

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2 

 

힙 삽입 과정 (max heap) 

시간 복잡도 : O(log₂n)

1. 새로운 노드는 완전 이진 트리의 삽입 규칙에 따라 왼쪽으로 추가
2. 부모노드와 비교하면서 재구조화 과정

* 재구조화 : 1. 부모 노드보다 수가 클 경우 부모 노드와 자식 노드 스왑
                2-1. 스왑될 경우. 부모노드에서 1번 반복
                2-2. 스왑되지 않을 경우. 재구조화 완료

 

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap

 

힙 삭제 과정

시간 복잡도 : O(log₂n)

1. 루트 노드를 삭제
2. 루트 노드 위치에 가장 말단노드로 대체
2. 재구조화 과정 수행

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap