- [ 목차 ]
- 힙이란 무엇인가 ?
- 힙을 이용한 우선순위 큐 구현
- 힙 구현과 성능
- 힙 정렬
- 제자리 힙 정렬
- 상향식 힙 생성
- 힙이란 무엇인가 ?
- 힙(Heap) : 내부노드에 키를 저장하며 다음 두 가지 속성을 만족하는 이진트리
- 힙 순서(Heap-order) : 루트를 제외한 모든 내부노드 v에 대해
Key(v) >= Key(parent(v)) => (최소힙 기준)
Key(v) <= Key(parent(v)) => (최대힙 기준)- 완전이진트리(Complete binary tree) : 힙의 높이가 h라고 하면
=> i = 0, ... , h - 1에 대해 깊이 i인 노드가 2^i개 존재
=> 깊이 h - 1에서, 내부노드들은 외부노드들의 왼쪽에 존재- 힙의 마지막(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를 삽입하는 것에 해당
- 삽입 알고리즘의 세 단계
- 삽입 노드 z, 즉 새로운 마지막 노드를 찾는다.
- k를 z에 저장한 후, expandExternal(w) 작업을 사용하여 z을 내부노드로 확장
- 힙 순서 속성을 복구
- 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은 힙으로부터 루트 키를 삭제하는 것에 해당 ( 최소 힙 기준 ! )
- 삭제 알고리즘의 세 단계
- 루트 키를 마지막 노드 w의 키로 대체
- reduceExternal(z) 작업을 사용하여 w와 그의 자식들을 외부노드로 축서
- 힙 순서 속성을 복구
- 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
반응형
'Algorithm Theory' 카테고리의 다른 글
| 해시테이블(Hash Table) (0) | 2020.12.13 |
|---|---|
| 이진탐색트리(Binary Search Tree) (0) | 2020.12.12 |
| 사전(Dictionary) (0) | 2020.12.12 |
| 우선순위 큐(Priority queue) (0) | 2020.09.24 |
| [ OT ] 들어가기전에.. (0) | 2020.09.24 |
