Algorithm Theory

힙과 힙정렬 ( Heap & Heap Sort )

Meng's Computer 2020. 9. 26. 04:47
  • [ 목차 ]
  • 힙이란 무엇인가 ?
  • 힙을 이용한 우선순위 큐 구현
  • 힙 구현과 성능
  • 힙 정렬
  • 제자리 힙 정렬
  • 상향식 힙 생성
  • 힙이란 무엇인가 ?
  • 힙(Heap) : 내부노드에 키를 저장하며 다음 두 가지 속성을 만족하는 이진트리

    1. 힙 순서(Heap-order) : 루트를 제외한 모든 내부노드 v에 대해
      Key(v) >= Key(parent(v)) => (최소힙 기준)
      Key(v) <= Key(parent(v)) => (최대힙 기준)
    2. 완전이진트리(Complete binary tree) : 힙의 높이가 h라고 하면
      => i = 0, ... , h - 1에 대해 깊이 i인 노드가 2^i개 존재
      => 깊이 h - 1에서, 내부노드들은 외부노드들의 왼쪽에 존재
    3. 힙의 마지막(Last Node) : 깊이 h - 1의 가장 오른쪽 내부노드

  • 힙의 높이
  • 정리 : n개의 키를 저장한 힙의 높이는 O(log n)이다.
  • 증명 : ( 완전이진트리의 성질을 이용 )

    • n개의 키를 저장한 힙의 높이를 h라 하자.
    • 깊이 i = 0, ... , h - 2 에 2^i개의 키, 그리고 깊이 h - 1에 적어도 한 개의 키가 존재하므로, n >= 1 + 2 + 4 + ... + 2^(h-2) + 1
    • 따라서, n >= 2^(h-1) (등비수열의 합) ,즉 h <= log(n) + 1

  • 힙과 우선순위 큐
  • 힙을 사용하여 우선순위 큐(Priority queue) 구현 가능
  • 전제 : 적정이진트리로 구현
  • 마지막 노드의 위치를 관리
  • 힙에 삽입
  • 우선순위 큐 ADT의 메쏘드 InsertItem 은 힙에 키 k를 삽입하는 것에 해당
  • 삽입 알고리즘의 세 단계
    1. 삽입 노드 z, 즉 새로운 마지막 노드를 찾는다.
    2. k를 z에 저장한 후, expandExternal(w) 작업을 사용하여 z을 내부노드로 확장
    3. 힙 순서 속성을 복구

  • Upheap ( Continue. 힙 삽입 )
  • 새로운 키 k가 삽입된 후, 힙 순서 속성이 위배될 수 있다.
  • upheap은 삽입노드로부터 상향경로를 따라가며 키 k를 교환함으로써 힙 순서 속성을 복구
  • upheap은 키 k가 루트에 또는 부모의 키가 k보다 작거나 같은 노드에 도달하면 정지 ( 최소힙 기준 ! , 최대힙은 반대 )
  • 힙의 높이는 O(log(n))이므로 upheap은 O(log(n))시간에 수행
    (앞서 배운, 선택정렬, 삽입정렬로 우선순위 큐와 비교했을 때 상당히 빠름)

  • 힙 삽입 알고리즘 ( PseudoCode )
[ PseudoCode ]
-----------------------------

Alg InsertItem(k)
	input Key k, node last
  	output none
    
advanceLast( )	// 마지막 노드위치를 찾음
z <- last		// 마지막 노드를 생성하고
Set node z to k	// 그 노드의 Key k를 대입
expandExternal(z) // z를 내부노드와 시킨다.
upHeap(z)	// 이 노드의 힙 속성에 맞게 재위치
return 

------------------------------

Alg upHeap(v)		// 최소 힙 기준
	input node v
    output none

if(isRoot(v))
	return
if(Key(v) >= Key(parent(v))
	return
swapElements(v,parent(v))
upHeap(parent(v))

-------------------------------
  • InsertItem 과 upHeap의 작업 대상 힙은 일반(generic)힙 이다.
    일반 힙이 무엇인지 모르겠다면, "우선순위 큐"
  • 힙 삽입 알고리즘 ( Continue. 힙 삽입 )
[ PseudoCode ]
--------------------------------------------

Alg expandExternal(z) { 연결리스트 경우만 ! }
	input external node z
    output none
    
l <- getnode()
r <- getnode()
l.right <- NULL
l.left <- NULL
l.parent <- z
r.right <- NULL
r.left <- NULL
r.parent <- z
z.left <- l
z.right <- r
return 

--------------------------------------------

: 내부노드화 시킨다는 소리

  • 힙 삭제
  • 우선순위 큐 ADT의 메쏘드 removeMin은 힙으로부터 루트 키를 삭제하는 것에 해당 ( 최소 힙 기준 ! )
  • 삭제 알고리즘의 세 단계
    1. 루트 키를 마지막 노드 w의 키로 대체
    2. reduceExternal(z) 작업을 사용하여 w와 그의 자식들을 외부노드로 축서
    3. 힙 순서 속성을 복구

  • DownHeap
  • 루트 키를 마지막 노드의 키로 대체한 후, 힙 순서 속성이 위배될 수 있다.
  • downheap은 루트로부터 하향 경로를 따라가며 키 k를 교환함으로써 힙 순서 속성을 복구
  • downheap은 키 k가 리프노드, 또는 자식의 키가 k보다 크거나 같은 노드에 도달하면 정지 ( 최소 힙 기준 !, 최대 힙은 반대 )
  • 힙의 높이는 O(log(n)) 이므로 downheap은 O(log(n)) 시간에 수행

  • 힙 삭제 알고리즘 ( 최소 힙 기준 )
[ PseudoCode ]     { 연결리스트 기준 }
----------------------------------------------------------
Alg removeMin()     { 최소 힙 기준 }
	input node last
    output key
    
k <- key(root())
w <- last
Set root to key(w)
retreatLast()
z <- rightChild(w)
reduceExternal(z)
downHeap(root())
return k

-----------------------------------------------------------

Alg downHeap(v)
	input node v whose left and right substrees are heaps
    out a heap with root v
    
if((isExternal(leftChild(v)) & isExternal(rightChild(v))
	return
smaller <- leftChild(v)
if(isInternal(rightChild(v))
	if(key(rightChild(v) < key(smaller))
    	smaller <- rightChild(v)
if(key(v) <= key(smaller))
	return
swqpElements(v,smaller)
downHeap(smaller)

-----------------------------------------------------------
  • ( Continue. 삭제 )
[ PseudoCode ] { 연결리스트 }
--------------------------------------------------------------------

Alg reduceExternal(z)	// 맨 마지막노드를 해제하고, 마지막노드 위치변경과정
	input external node z
    output the node replacing the parent node of the removed node z
    
w <- z.parent
zs <- sibling(z)
if(isRoot(w))
	root <- zs
    zs.parent <- NULL
else
	g <- w.parent
    zs.parent <- g
    if(w = g.left)
    	g.left <- zs
    else  // w = g.right
    	g.right <- zs
putnode(z)		// 해제 z
putnode(w)		// 해제 w
return zs

-----------------------------------------------------------------------

  • 마지막 노드 갱신
  • O(log(n))개의 노드를 순회함으로써 삽입 노드를 찾을 수 있다. (advanceLast)
    • 현재 노드가 오른쪽 자식인 동안, 부모 노드로 이동
    • 현재 노드가 왼쪽 자식이면, 형제 노드로 이동
    • 현재 노드가 내부노드인 동안, 왼쪽 자식으로 이동
  • 삭제 후 마지막 노드를 갱신하는 작업은 위한 반대 방향으로수행 (retreatLast)

  • 배열에 기초한 힙 구현
  • n개의 키를 가진 힙을 크기 n의 배열을 사용하여 표현 가능
  • 첨자 i에 존재하는 노드에 대해
    • 왼쪽 자식은 첨자 2*i 에 존재
    • 오른쪽 자식은 첨자 2*i+1 에 존재
    • 부모는 첨자 i/2에 존재
  • 노드 사이의 링크는 명시적으로 저장할 필요가 없다.
    ( 다만, 머리 속으로 링크가 있는 것처럼 상상하자.)
  • 외부노드들은 표현할 필요가 없다.
  • 첨자 0 셀은 사용하지 않는다. ( 빈 노드 )
  • 마지막 노드의 첨자 : 항상 n
    • InsertItem : 작업은 첨자 n + 1위치에 삽입하는 것에 해당
    • removeMin : 작업은 첨자 n 위치에서 삭제하는 것에 해당

  • 성능 요약

  • 힙 정렬 ( Heap Sort ) ( 최소힙 기준 )
  • 힙을 사용하여 구현된 n-항목 우선순위 큐를 고려하면,
    • 공간 사용량은 O(n)
    • InsertItem 메쏘드와 removeMin 메쏘드는 O(log(n))시간에 수행
    • size, isEmpty,minKey,minElement 메쏘드는 O(1)시간에 수행
      ( 힙의 루트노드정보만 조회하면 되니깐 )
  • 힙에 기초한 우선순위 큐를 사용함으로써, n개의 원소로 이루어진 리스트를 O(log(n))시간에 정렬할 수 있다.
    • 선택정렬이나 삽입정렬과 같은 2차 정렬 알고리즘보다 훨씬 빠르다.
  • 이 알고리즘을 힙 정렬(Heap Sort) 라고 한다.
[ PseudoCode ]
---------------------------------

Alg heapSort(L)
	input list L
    output sorted list L
    
H <- empty heap
while(!L.isEmpty())  { 1 단계 }
	k <- L.removeFirst()
    H.insertItem(k)
while(!H.isEmpty())  { 2 단계 }
	k <= H.removeMin()
    L.addLast(k)
return

---------------------------------
  • 힙 정렬 개선
  • Heap Sort 의 성능 향상을 위한 두 가지 개선점
    • 제자리 힙 정렬은 heap sort 의 공간 사용을 줄인다.
    • 상향식 힙 생성은 heap sort의 속도를 높힌다.
  • 제자리 힙 정렬
  • 이 방식은 정렬되어야 할 리스트가 "배열" 로 주어진 경우에만 적용
  • 힙을 저장하는데 리스트 L의 일부를 사용함으로써 외부 힙 사용을 피한다.
  • 지금까지 사용했던 최소힙(min-heap) 대신, 최대 원소가 맨위에 오게 되는 최대힙(max-heap)을 사용
[ PseudoCode ]
---------------------------------------------------------------

Alg InPlaceHeapSort(A)
	input array A of n Keys
    output sorted array A
    
buildHeap(A)	// { 1 단계 }
for i <- n downto 2	 // { 2 단계 }
	A[1] <-> A[i]
    downHeap(1, i-1)
return

----------------------------------------------------------------

Alg buildHeap(A)
	input array A of n Keys
    output heap A of size n

for i <- 1 to n
	insertItem(A[i])
return

----------------------------------------------------------------

Alg downHeap(i, last)
	input index i of array A representing a maxheap of size last
    output none
    
left <- 2i
right <- 2i + 1
if(left > last)
	return
greater <- left
if(right <= last)
	if(key(A[right] >= key(A[greater]))
    	greater <- right
if(key(A[i] >= key(A[greater]))
	return
A[i] <-> A[greater]
downHeap(greater,last)

---------------------------------------------------------------
  • 제자리 힙 정렬 ( Continue. )
  • 알고리즘 수행의 어떤 시점에서든
    • L의 첨자 1부터 i까지의 왼쪽 부분을 힙의 원소들을 저장하는데 사용
    • 그리고 첨자 i+1부터 n까지의 오른쪽 부분을 리스트의 원소들을 저장하는데 사용
  • 그러므로, L의 (첨자 1, ... , i에 있는) 첫 i개의 원소들은 힙의 배열 표현
    => 즉, 첨자 k의 원소는 첨자 2k 및 2k+1의 자식들보다 크거나 같다.

  • 제자리 힙 정렬 ( Continue. )
  • 1기
    • 비어 있는 힙으로부터 출발하여 힙과 리스트의 경계를 왼쪽에서 오른쪽으로 한 번에 한칸씩 이동
    • 단계 i(i =1, ... , n)에서, 첨자 i에 있는 원소를 힙에 추가함으로써 힙을 확장
  • 2기
    • 비어 있는 리스트로부터 출발하여 힙과 리스트의 경계를 오른쪽에서 왼쪽으로 한 번에 한 칸씩 이동
    • 단계 i(i = n, ... , 2)에서, 힙의 최대 원소를 삭제하여 리스트의 첨자 i에 저장함으로써 리스트를 확장
  • 제자리 힙 정렬 예
  • 1기의 2기의 각 단계에서, 배열 가운데 힙에 쓰인 부분을 파란색 원소로 표시
  • 아래 점선 내에 보인 이진트리 관점의 힙은 가상적일 뿐, 제자리 알고리즘에 의해 실제 생성되지는 않음에 유의 ( 배열로 구현했으니 )
  • 1기 작업 시작
  • 1기 작업 완료
  • 리스트가 최대 힙으로 변환됨
  • 2기 작업 시작

 

  • 상향식 힙 생성
  • heap-sort의 1기에서, n회의 연속적인 InsertItem 작업을 사용하여 O(nlog(n)) 시간에 힙을 생성했다.
  • 대안으로, 만약 힙에 저장되어야 할 모든 키들이 미리 주어진다면, O(n)시간에 수행하는 상향식 힙 생성 방식있다. ( 뒤에 기술함. )
[ PseudoCode ]
----------------------------------------------------------------------------------

Alg buildHeap(L)		// ( 재귀적, 배열인경우 )
	input list L storing n Keys
    output heap T storing the Keys in L

if(L.isEmpty())
	return empty heap
Remove the first key km from L
Split L into two sublists, L1, and L2, each of size (n-2)/2 approximately

T1 <- buildHeap(L1)
T2 <- buildHeap(L2)

Create a binary tree T with root r storing k, left subtree T1, and right subtree T2

downHeap(r)
return T

------------------------------------------------------------------------------------
  • log n 단계만을 사용하여 주어진 n개의 키를 저장하는 힙 생성 가능
  • 단계 i에서, 각각 2^i - 1 개의 키를 가진 두 개의 힙을 2^(i+1) -1개의 키를 가진 힙으로 합병

  • 두 개의 힙을 합병
  • 두 개의 힙과 키 k가 주어졌을 때
  • k를 저장한 노드를 루트로, 두 개의 힙을 부트리로 하는 새 힙을 생성
  • 힙 순서 속성을 복구하기 위해 downheap을 수행

  • "상향식" 이라 불리는 이유
  • 상향식 힙 생성버전은 각 재귀호출이 힙인 부트를 반환하는 방식이기 때문에 "상향식" 이라 불린다.
  • 다시 말해, T 의 힙합(heapification)는 외부노드에서 시작하여, 각 재귀호출이 반환함에 따라 트리 위쪽으로 진행
  • 이 때문에 종종 힙화한다(heapify)고 말하기도 한다.

  • 비 재귀적 상향식 힙 생성
  • 상향식 힙생성의 비재귀 버전
  • 정렬되어야 할 리스트가 "배열"로 주어진 경우에만 적용
  • 비 재귀적 힙 생성 절차가 "내부노드를 왼쪽 자식으로 가지는, 가장 깊은 내부노드 가운데 가장 오른쪽 노드"에서 시작하여 루트로 향하는 후진 방향으로 반복수행
    ( = 리프노드가 아닌, 바로 전 높이에서 가장 오른쪽 노드를 의미함.
    왜냐면, 리프노드는 downheap 할 것이 없으니깐 )
  • 시작 노드 : 첨자 [n/2] 인 노드
[ PseudoCode ]
-----------------------------

Alg buildHeap(A)		// 비재귀적 힙생성, 배열인 경우
	input array A of n Keys
    output heap A of size n
    
for i <- [n/2] downto 1
	downHeap(i,n)

return

------------------------------
  • 실질적 구현단계 ( 삽입식 힙 생성. C ver. )
  • 알고리즘 구현 전에 설계 팁
[ PseudoCode ]
----------------------------------------------

Alg InsertItem(key)		// 힙 삽입
	input integer key array H 	// key: 삽입 키
    output array H		// H: 전역배열, heap
    
n <- n + 1		// n 갱신
H[n] <- key		// 힙에 초기 삽입 위치는 n
upHeap(n)		// 힙 조정
return

-----------------------------------------------

Alg removeMax()			// 힙 삭제 ( 최대 힙 기준 )
	input array H	
    output array H		// H: 전역배열, heap
    
key <- H[1]		// 루트키 보관
H[1] = H[n]		// 힙의 마지막 키를 루트로 이동
n <- n + 1		// n 갱신
downHeap(1)		// 힙 조정
return key

------------------------------------------------
  • Code
// < 힙생성 >
// 배열(순차트리)의 형태 힙(순차 힙)생성 문제. ( # 연결리스트의 형태 힙 = 연결 힙 )
// 루트의 최소 키 저장 시 = 최소 힙(min-heap)
// 루트의 최대 키 저장 시 = 최대 힙(max-heap)
// 힙 생성 => 1. 삽입식(Insertion) 2. 상향식(bottom-up)
// 1.삽입식 = 모든 키들이 미리 주어진 경우, or 키들이 차례로 주어지는 경우
// 2.상향식 = Only 미리 키들이 미리 주어진 경우
// 동일한 키들의 동일 순서로 구성된 초기 리스트라도 삽입식, 상향식 중 어느 방식을 적요하느냐에 따라 상이한 힙이 생성 될 수 있다.
// 힙은 적정이진트리로 생성하기 떄문에 배열로 구현시 같은 레벨노드들의 키값을 출력하는 것이 쉽다
// ( 삽입식 힙생성, (키 값들이 순서대로 입력되는 경우 )
#include<stdio.h>

int n = 0;			// 키 값수 제어 변수 n
int arr[100];		// 빈 초기리스트

voidinsertItem(int key);	// 키 삽입
intremoveMax();	// 키 삭제
voidupHeap(int idx);	// idx에 저장된 키를 크기에 맞는 위치로 상향이동
voiddownHeap(int idx);	// idx에 저장된 키를 크기에 맞는 위치로 하향이동
voidprintHeap();	// 힙 요소들 레벨순서에 맞게 출력

intmain(){
	int key;
	char op;

	do
	{
		scanf("%c",&op);
		switch (op)
		{
		case 'i':
			scanf("%d", &key);
			insertItem(key);
			break;
		case 'd':
			printf("%d\n",removeMax());
			break;
		case 'p':
			printHeap();
			break;
		}
		getchar();
	} while (op != 'q');
	
	return 0;
}

voidinsertItem(int key){
	arr[n+1] = key;	// 마지막 노드 위치에 키캆 삽입
	upHeap(n+1);	// upHeap을 통해서 방금 마지막노드의 삽입된 키 값이, 최대힙 기준에 맞게 제자리 위치로 찾아감, 참고로 upHeap은 재귀
	n = n + 1;		// upHeap이 끝난 뒤에 노드의 개수 1증가
	printf("%d\n", 0);
}
intremoveMax(){
	int key = arr[1];	// 삭제될 키 값( 즉, 힙의 루트노드 키값 )을 따로 저장
	arr[1] = arr[n];	// (최대 힙기준) 루트노드에있는 키 값과, 마지막 노드 키값을 교환
	downHeap(1);	// 마지막노드의 키값이 루트노드의 키 값으로 대체된 후, 자기 자리에 맞는 위치로 찾아가게 dowmHeap
	n = n - 1;	// downHeap끝나고 전체 노드수 -1;
	return key;
}
voidupHeap(int idx)// ( 최대힙 생성 기준 ){
	int max;	// 최대값 저장 변수
	if (idx != 1)	// 루트노드 하나있을때 제외하고
	{
		if (arr[idx] >= arr[idx / 2])	// 현재 본인위치의 키값과, 본인의 부모노드의 키값을 비교해서 자기가 더 크면
		{
			max = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = max;	// 키 값 서로 교환하고
			upHeap(idx / 2);	// 본인의 부모노드 기준으로 upHeap재귀호출
		}
	}
}
voiddownHeap(int idx)// ( 최대힙 생성 기준 ){
	int greater,tmp;
	
	if (n >= idx * 2)	// 전체 노드수가 최소 본인의 왼쪽자식노드는 있을 경우에 들어간다
	{
		greater = idx * 2;	// 최대 키 값 위치 저장
		if (n >= idx * 2 + 1)	// 본인의 오른쪽 자식노드도 존재하면
			if (arr[idx * 2 + 1] > arr[greater])	// 왼쪽 노드와 오른쪽 노드중 키값이 더 큰 노드의 위치 저장
				greater = idx * 2 + 1;
		if (arr[idx] < arr[greater])	// 본인의 키 값과, 본인의 좌우 자식노드중에 더 큰 키값을 가진 노드의 키값과 비교해서 본인이 작으면
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;	// 더 큰 키값을 본인 위치로 올리고, 본인 키값은 그 자식노드의 키값으로 내린다.
			downHeap(greater);	// 그 후, 그 자식노드 기준으로 downHeap재귀호출
		}
	}
}
voidprintHeap(){
	for (int i = 1; i <= n; i++)
		printf(" %d", arr[i]);
	printf("\n");
}
  • 실질적 구현단계 ( 상향식 힙생성 (재귀,비재귀). C ver. )
  • 구현전에 설계 팁
[ PseudoCode ]
-------------------------------------------------------------------

Alg rBuildHeap(i)		// 힙생성 - 재귀버전
	input integer i, array H		// i: 현재 부트리의 루트 인덱스
	output array H		// H:전역 배열, heap
    
if(i > n)		// n: 전역변수
	return
rBuildHeap(2i)		// 현재 부트리의 좌 부트리를 힙 생성
rBuildHeap(2i + 1)		// 현재 부트리의 우 부트리를 힙 생성
downHeap(i)			// 현재 부트리의 루트와 좌우 부트리를 합친 힙 생성
return

---------------------------------------------------------------------

Alg buildHeap()		// 힙생성 - 비재귀버전
	input array H	// H: 전역배열, heap
	output array H
    
for i <- n/2 downto 1 	// n: 전역변수, 마지막 내부노드부터 역방향 루트까지
	downHeap(i)
return 

---------------------------------------------------------------------
  • C Code ( 상향식 힙생성 - 재귀 )
// 상향식 힙생성 ( ver.재귀 )
#include <stdio.h>

int arr[100],n= 0;	// 배열의 최대 원소개수는 100개 미만
void rBuildHeap(int idx);	// 재귀형태 상향식 힙 생성
void downHeap(int idx);	// 다운 힙
void printHeap();	// 원소출력

int main()
{
	int keyCount;		// key원소 수 
		
	scanf("%d", &keyCount);	// key원소 수 입력
	for (int i = 1; i <= keyCount; i++)	// 0번째 인덱스원소는 비워놓고 1번째 인덱스위치부터 키값 삽입
		scanf("%d", &arr[i]);
	n = keyCount;	// 순차힙 전체크기를 키수 만큼 초기화
	rBuildHeap(1);	// 재귀 상향식 힙 생성
	for (int i = 1; i <= keyCount; i++)	// 생성 된 힙의 키값들 출력
		printf(" %d", arr[i]);
	return 0;	// 메인종료
}
void rBuildHeap(int idx)	// 상향식 힙 생성함수 ( 재귀 )
{
	if (idx <= n)	// 인자로 들어온 인덱스가 전체 키수보다 작거나 같을때까지 ( = 내부노드일 경우 )
	{
		if(idx*2 <= n)	// 현재 인덱스(i)의 왼쪽자식노드인덱스(2i)가 전체 키의 수보다 작거나 같으면
			rBuildHeap(idx * 2);	// 현재 인덱스(현재 노드)의 왼쪽자식인덱스 기준으로 rBuildHeap 재귀호출
		if(idx*2 + 1 <= n)	// 이것은 위에 설명과 같게, 오른쪽 자식노드의 경우
			rBuildHeap(idx * 2 + 1);
	}
	downHeap(idx);	// 부트리 기준으로 downHeap실행 ( root노드부터 리프노드 전 까지 downHeap 실행되는데 )
}
/*
n개의 노드에 대해 height가 0인 리프노드부터  각 height의 노드의 개수는 (n/2^(h+1))개이고 
상향식 힙생성에서 Height에 대해 리프노드들은 downHeap을 실행하지않는다 == 0
그 다음 높이부터는 자신의 바로 아래 자식노드까지만 downHeap을 하면되고 == 1
이 방식대로 높이가 h인 루트노드에 대해서는 downHeap을 h번하면 된다.
이 과정을 정리하면 리프노드부터 downHeap이 실행되니깐
( n/2^(1) * 0 ) + ( n/2^(2) * 1 ) + ... + ( n/2^(h+1) * h ) ==> O(n)만큼의 downHeap이 실행될 것이다.
downHeap코드의 가장 바깥쪽 조건문에서 이 과정이 진행된다.
*/
void downHeap(int idx)	// (최대힙기준)downHeap
{
	int greater, tmp;	// 본인의 왼쪽,오른쪽 자식노드중 더 큰 키값을 가진 자식노드의 인덱스(노드) 위치를 저장변수

	if (n >= idx * 2)	// 최소 자신의 왼쪽자식노드가 존재할경우 
	{
		greater = idx * 2;	// 일단 최대 키 인덱스는 왼쪽 자식으로하고
		if (n >= idx * 2 + 1)	// 오른쪽 자식도 있는데
			if (arr[idx * 2 + 1] > arr[greater])	// 왼쪽 자식보다 키값이 크면
				greater = idx * 2 + 1;	// 최대 키 인덱스 오른쪽자식노드로 변경
		if (arr[idx] < arr[greater])	// 이제 본인의 키값과 비교해서 자기 자식의 노드보다 작으면
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;	// 두 노드의 키값을 swap
			downHeap(greater);	// swap 한 자식을 기준으로 downHeap재귀
		}
	}
}
void printHeap()		// 생성 된 힙 키 값 출력
{
	for (int i = 1; i <= n; i++)	
		printf(" %d", arr[i]);
	printf("\n");
}
  • C Code ( 상향식 힙생성 - 비재귀 )
// 상향식 힙 생성 ( ver.비재귀 )
#include <stdio.h>

int arr[100], n = 0;

void buildHeap();	// 비재귀형태 상향식 힙 생성
void downHeap(int idx);
void printHeap();

int main()
{
	int keyCount;		// key원소 수 

	scanf("%d", &keyCount);	// key원소 수 입력
	for (int i = 1; i <= keyCount; i++)	// 0번째 인덱스원소는 비워놓고 1번째 인덱스위치부터 키값 삽입
		scanf("%d", &arr[i]);
	n = keyCount;	// 순차힙 전체크기를 키수 만큼 초기화
	buildHeap();	// 비재귀 상향식 힙 생성
	for (int i = 1; i <= keyCount; i++)	// 생성 된 힙의 키값들 출력
		printf(" %d", arr[i]);
	return 0;	// 메인종료
}

void buildHeap()	// 상향식 힙생성 ( 비재귀적 )
{
	for (int i = n / 2; i >= 1; i--)	// 리프노드 바로 위층 내부노드중에 왼쪽 자식노드가 있는 순서상 가장 마지막 내부노드부터 시작해서 루트노드까지 downHeap을 실행한다.
		downHeap(i); 
}
/*
n개의 노드에 대해 height가 0인 리프노드부터  각 height의 노드의 개수는 (n/2^(h+1))개이고
상향식 힙생성에서 Height에 대해 리프노드들은 downHeap을 실행하지않는다 == 0
그 다음 높이부터는 자신의 바로 아래 자식노드까지만 downHeap을 하면되고 == 1
이 방식대로 높이가 h인 루트노드에 대해서는 downHeap을 h번하면 된다.
이 과정을 정리하면 리프노드부터 downHeap이 실행되니깐
( n/2^(1) * 0 ) + ( n/2^(2) * 1 ) + ... + ( n/2^(h+1) * h ) ==> O(n)만큼의 downHeap이 실행될 것이다.
downHeap코드의 가장 바깥쪽 조건문에서 이 과정이 판단된다.
*/
void downHeap(int idx)	// 재귀적 상향식 힙생성의 downHeap설명과 동일해서 생략
{
	int greater,tmp;
	if (n >= idx * 2)
	{
		greater = idx * 2;
		if (n >= idx * 2 + 1)
			if (arr[greater] < arr[idx * 2 + 1])
				greater = idx * 2 + 1;
		if (arr[idx] < arr[greater])
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;
			downHeap(greater);
		}
	}
}
void printHeap()	// 재귀적 상향식 힙생성의 printHeap설명과 동일해서 생략
{
	for (int i = 1; i <= n; i++)
		printf(" %d", arr[i]);
	printf("\n");
}


728x90
반응형