[강의노트] 힙과 힙정렬 - 3

힙과 힙정렬 - 3

아래의 글에 이어지는 글입니다. 

[강의노트] 힙과 힙정렬 - 1

 

[강의노트] 힙과 힙정렬 - 2

 

상향식 힙 생성

https://man-25-1.tistory.com/156

[실습] 상향식 힙 생성

위의 실습에서 상향식 힙 생성에 대해 자세히 이해하는 시간을 가졌었다.

코드로 작성한 내용을 formal 하게 정리해보자.

 

이전 포스트에서 힙 정렬의 개선점에서 논했을 때, 두가지가 있었다.

하나는 외부공간을 사용하지않는 제자리 정렬

나머지 하나는 삽입식 힙 생성이 아닌 상향식 힙 생성을 통해 알고리즘 효율을 높이는 것이었다.

 

상향식 힙생성의 처음에 리스트를 완전이진트리로 전환하는 알고리즘 convertToCompleteBinaryTree 가 등장한다

 

연결리스트를 가지고 상향식 힙생성을 할때는 전환 작업이 필요하다. 스스로 작성해보자.

 

상향식 힙생성에서 두개의 힙을 합병한다는 개념이 나오는데, 아래의 설명처럼

두개의 힙이 존재하고, 키 k가 루트노드로 존재할때, 두개의 힙을 부트리로 하는 새 힙을 생성하는 과정을 합병한다고 함.

 

그럼 왜 상향식이라고 불릴까? 각 재귀호출이 부트리에 해당하는 힙을 반환하는 방식때문에 상향식이라고 불린다.

각 재귀호출이 트리의 가장 왼쪽 하단에서 오른쪽 위로 상승하면서 힙화가 진행되기때문에 상향식 !

 

물론 비재귀적으로도 상향식 힙생성 알고리즘을 작성할 수 있다. 

출발지점은 내부노드를 왼쪽 자식으로 가지는 가장 깊은 내부노드 가운데 가장 오른쪽 노드가 된다.

즉 위의 그림에서는 인덱스3에 해당하는 key : 2 에서 출발

상향식 힙생성은 O(n) 시간 , 삽입식 힙 생성은 O(n *log n) 시간 !