힙(Heap)의 구조와 동작과정

나머지는 관심없고 부모노드만 알고싶은  힙(Heap) 

 

힙(Heap)이란

(max-heap)일 경우, 루트노드가 가장 큰 노드이고,

(min-heap)일 경우, 루트노드가 가장 작은 노드이다. 

 

따라서 루트노드를 제외하고 나머지 노드의 관계는 알 수도 없고, 중요하지도 않다. 

 

 

어떻게 힙 자료구조가 동작하는지 알아보자.

 

 

* 힙의 삽입 과정 (max-heap 기준)

 

1) 완전이진트리의 형태이므로 리프노드 자리중 다음 노드 자리에 일단 new Node 삽입

 

2) 부모노드와 비교했을때 삽입한 노드가 더 크다면 부모노드와 스왑, 아니면 그대로

 

3) 더 큰 부모노드를 만날때까지 2번을 반복한다, 루트노드까지 간다면 거기서 종료

 

 

 

 

위 과정을 그림으로 나타내면 다음과 같다. 

 

 

 

 

---

 

 

 

 

* 힙의 삭제 과정 (max-heap 기준)

 

1) 루트노드 값이 필요하다면 다른 변수에 저장

 

2) 루트노드 자리에 순서상 가장 마지막에 있는 노드를 대입

 

3) 자식 노드들과 비교하며 더 큰값을 위로 올림 

 

4) 3번과정을 반복하며 모든 자식노드와 비교했을때 본인이 더 크다면 종료

 

 

 

 

위 과정을 그림으로 나타내면 다음과 같다. 

 

 

*여기서 주의할 점은 힙은 루트 노드를 기준으로 만들어진 자료구조이기 때문에 루트노드만 삭제할 수 있다는점이다. 

 

 

 

각 동작의 시간복잡도를 정리해보면 다음과 같다. 

 

삽입 -> O(logn), 리프노드부터 루트까지 올라오며 비교했을때가 최악의 경우

삭제 -> O(logn), 루트노드 삭제후, 루트노드부터 리프노드까지 갔을때가 최악의 경우