[실습] 상향식 힙 생성

상향식 힙 생성

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

[실습] 삽입식 힙 생성

저번 포스트에서 다루었던 삽입식 힙 생성에 이어서 이번에는 상향식 힙 생성을 다루어보자.

힙 생성에 대한 전반적인 이야기는 위 게시물을 참고하면 되고, 이번에는 삽입식 힙 생성과 상향식 힙 생성의 차이점에

중점을 두고 다루어보겠다.

힙 생성은 삽입식과 상향식의 두 가지 방식이 있다. 삽입식은 모든 키 들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 양쪽에 적용이 가능하다. 상향식은 모든 키 들이 미리 주어진 경우에만 적용 가능하다.

따라서 상향식 힙 생성의 경우 모든 키들이 미리 주어진 경우에 사용할 수 있다.

프로그래밍 조건

1) 키들이 미리 한꺼번에 주어진다. 사용자로부터 입력받은 키들을 배열에 저장한다.

2) 초기 배열에 저장된 키들을 상향식으로 재배치하여 힙을 생성한다.

   상향식 힙 생성을 위한 재귀 또는 비재귀 방식의 알고리즘 가운데 어느 전략을 사용해도 좋다.

3) 참고로 재귀, 비재귀 두 가지 방식 모두 O(n) 시간에 수행 가능하므로 그렇게 되도록 작성해야 한다.

 

main() 함수

- 인자: 없음

- 반환값: 없음

- 내용: rBuildHeap(1) 또는 buildHeap() 호출하여 힙 생성 후, 힙을 인쇄하고 종료.

1 2 3 4 5 6 7 8 9 10 11

int main() {       scanf("%d", &n);     //Heap의 인덱스 0은 비워둔다       for (int i = 1; i <= n; i++) {         scanf("%d", &Heap[i]);     }     buildHeap();     printHeap(); } Colored by Color Scripter

cs

rBuildHeap은 재귀, buildHeap은 비재귀 방식의 상향식 힙 생성이다.

BuildHeap(i) 함수

- 인자: 정수 i (부분 힙의 루트 인덱스)

- 반환값: 없음

- 내용: 비재귀 방식으로 상향식 힙 생성

- 시간 성능: O(n)

 

1 2 3 4 5 6 7

void buildHeap() {       for (int i = n / 2; i >= 1; i--) {         downHeap(i);     }   } Colored by Color Scripter

cs

downHeap은 지난 포스트인 삽입식 힙에서 다루었으므로 생략하겠다. 

따라서 위의 코드는 i=n/2 지점에서 루트노드까지 상향식 이동하면 각 인덱스에서 downheap을 수행하라는 뜻인데

직관적으로 잘 와닿지 않을 수 있다. 따라서 예시를 통해 이해하면 수월하다

 

아래의 예시를 보자.

heapify가 되지않은 채로 13개의 키 값을 무작위 순서로 사용자에게 입력받은 것이다. 따라서 힙의 개수를 나타내는 변수 n은 현재 13이다.

코드를 살펴보자

for(int i = n/2 ; i>=1 ; i--){          downheap(i); }

위의 예시에서는 i=6부터 i=1까지 각 노드에서 downheap을 실행하게 된다. 즉 다시 말하자면, 힙트리에 마지막 내부노드부터 루트노드까지 상향이동하며 downheap을 실행하는 것이다. 

한번 그 과정을 살펴보면서 이해해보자

 

 

 

 

i=6 에서의 downheap(i) 수행결과

 

i=5 에서의 downheap(i) 수행결과

 

i=4 에서의 downheap(i) 수행결과

i=3 에서의 downheap(i) 수행결과

(이미 최대힙구조를 만족하므로 변화 없음)

 

i=2 에서의 downheap(i) 수행결과

 

i=1(루트노드) 에서의 downheap(i) 수행결과

각 내부노드들에서만 수행했음에도 결과는 최대 힙구조가 되었다. 자식노드를 가진 노드에서만 downheap을 수행하면 되므로

n/2가 사실은 힙에서의 마지막 내부노드를 가리키는 인덱스라는 사실을 어렵지않게 받아들일 수 있을 것이다.

 

이렇게 비재귀형식으로 상향식 힙 생성을 구현하는 것은 위의 원리만 이해한다면 매우 쉽게 구현할 수 있다.

rbuildHeap() 함수

- 인자: 없음

- 반환값: 없음

- 내용: 재귀 방식으로 상향식 힙 생성

- 시간 성능: O(n)

 

재귀방식 알고리즘이 수도코드로 나와있다. 재귀적인 구조를 잘 파악하기위해서는 base case와 recursive case를 구분해야한다. 

base case는 i 가 n보다 큰 경우가 되고 recursive case는 rBuildHeap을 2i와 2i+1의 매개변수에 대해서 재 호출하고, downHeap(i)를 호출하는것이다.

재귀호출 과정을 따라가보면 비재귀에서 다룬 아래의 코드와 같게 된다

for(int i = n/2 ; i>=1 ; i--){          downheap(i); }

그래서 위와 마찬가지로 이해하면 된다.

 

 downHeap(i) 함수 

이전 포스트에서 다루었으므로 설명 생략.

printHeap() 함수

 

설명 생략