힙과 힙정렬 ( Heap & Heap Sort )

• [ 목차 ]

• 힙이란 무엇인가 ?
• 힙을 이용한 우선순위 큐 구현
• 힙 구현과 성능
• 힙 정렬
• 제자리 힙 정렬
• 상향식 힙 생성

• 힙이란 무엇인가 ?

• 힙(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");
}