What is Heap?
-
완전 이진 트리(complete binary tree)이며, 중복된 값을 허용한다.
이진 탐색 트리에서는 중복된 값을 허용하지 않았다.
-
최대 히프(max heap) or 최소 히프(min heap)
- 최대 히프 : 부모 노드의 키값 >= 자식 노드의 키값, 루트 노드 : 최대값
- 최소 히프 : 부모 노드의 키값 <= 자식 노드의 키값, 루트 노드 : 최소값
-
느슨한 정렬 상태를 유지한다.
- 느슨한 정렬
큰 값이 상위 레벨이고 작은 값이 하위 레벨에 있다는 정도의 정렬상태
Heap operations
히프 추가(insert) 연산과 추출(extract) 연산을 할 때 머릿속에 히프의 특징을 만족시켜야만 한다고 생각하고 있으면 편하게 연산을 할 수 있을 것입니다.
- insert
- 새로운 데이터를 인덱스 순으로 가장 마지막 위치에 삽입한다.
- 추가된 데이터를 부모 노드와 비교한뒤, 순서가 올바른 경우 중지한다
- 그렇지 않다면, 데이터를 부모 노드와 바꾸고, 2번으로 돌아간다
만약 LEFT노드 에서 부모노드 보다 데이터가 커서 데이터를 올렸지만 Right노드보다 작다면? 이것을 검사하지는 않는데 이진 트리의 유효성을 어떻게 확인 할 것인가?
- => 생각의 시작부터 멍청했다.
LEFT 노드에 데이터를 넣는다 == RIGHT 노드가 존재하지 않는다
- 느슨한 정렬상태이기 때문에 LEFT가 RIGHT보다 클 수도 있다.
시간복잡도 : O (log n )
삽입 연산은 새로운 데이터와 부모 노드만 비교하며 트리를 타고 올라가게 된다.
이때, 최악의 경우는 루트 노드까지 비교연산을 한 경우이다.
그러므로 완전 이진 트리의 높이가 log n 이므로, 시간 복잡도는 O (log n ) 만큼만 소요된다.
- extract(delete)
-
힙의 루트에 있는 데이터를 삭제하고, 마지막 인덱스의 데이터를 루트로 올린다.
-
새로운 루트노드와 자식 노드를 비교한다. 순서가 올바른 경우 중지한다.
이때, 최대 히프라면 자식 노드 중 더 큰 노드와 비교한다.
최소 히프라면 자식 노드 중 더 작은 노드와 비교한다.
-
그렇지 않다면, 비교한 자식 노드와 루트 노드를 교환하고 2번으로 돌아간다.
-
그렇지 않다면, 비교한 자식 노드와 루트 노드를 교환하고 2번으로 돌아간다.
이러한 삽입연산과 삭제연산의 과정을 Heapify라고 한다.
시간복잡도 : O (log n )
삭제 연산도 마찬가지로 루트 노드부터 자식노드와 비교하며 내려가는 구조이기 때문에
최악의 경우 역시 트리의 높이에 해당하는 시간이 걸린다
삭제 연산 역시, 트리의 높이가 log n 이므로, 시간 복잡도는 O (log n ) 만큼만 소요된다.