3. 상향식 힙정렬

🔍상향식 힙생성

원래 사용하던 힙생성 알고리즘의 경우 삽입식 힙생성 알고리즘이다.

만약, 힙에 저장되어야 할 모든 키들이 미리 주어질 경우,

O(n)시간에 수행하는 상향식 생성 방식을 사용할 수 있다.(원래는 O(n log n)시간 사용)

1. 주어진 리스트(배열, 리스트)를 완전 이진트리로 전환시킨다.
   1. 배열: 입력 배열 L의 첫번째 원소를 루트로 하는 완전 이진트리로 볼 수 있다.
   2. 연결리스트: 전환 작업 수행에 O(n)시간이 소요된다.(일반 연결리스트를 완전이진트리로 전환)
2. rBuildHeap()을 재귀호출
   1. log n단계로 n개의 키를 저장하는 힙 생성 가능
   2. i번째 단계에서, 각각 2^i - 1개의 키를 가진 두개의 힙을 합병하여 2^(i+1) -1개의 키를 가진 힙이됨.

• 위처럼 힙을 합병해가며 힙을 만들어감.
• 이렇게 위쪽으로 가면서 힙을 확장해가는 힙을 상향식 힙생성이라한다.

과정

1. 위처럼 완전 이진 트리가 존재할때

2. 왼쪽 맨아래 두 노드에 부모를 붙여 작은 힙을 생성한다.

3. 옆 서브트리도 똑같이 알고리즘 적용 이후 두 힙에 부모를 붙여 큰 힙을 생성

4. 다른 서브트리도 마찬가지로 진행후 병합.

삽입식, 상향식 힙생성의 시간 차이

downheap의 최악의 경우 시간을 대리경로를 사용하여 시각화할때

이 대리경로는 먼저 오른쪽 자식노드로 이동한 후 힙의 바닥까지 반복적으로 왼쪽 자식노드를 따라 이동,

각 노드는 위 화살표처럼 최대 두개의 대리경로에 의해 순회되므로, 대리경로들의 전체 노드수는 O(n)

• 따라서 상향식 힙생성은 O(n)시간에 수행
• 하지만 힙 정렬의 경우 2phase의 최악 실행시간은 n log n이다.
• 그래도 힙정렬의 속도를 상향시키는데 도움을 준다.