힙 편집하기

;Heap
;값을 노드 단위로 두고 노드들 가운데서 큰 값 또는 작은 값을 가지는 노드를 빠른 시간 내에 찾아내거나 정렬할 수 있도록 구성된 [[완전 이진 트리]]

* ;A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
* 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

== Heap의 종류 ==
* 최대 힙(Max Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
* 최소 힙(Min Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙

== Heap의 연산 시간 ==
* n개의 노드에 대해 구성 복잡도(삽입, 삭제 시간)은 O(logn)

== Heap의 구현 ==
* 힙을 저장하는 표준적인 자료구조는 배열 이다.
* 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
* 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
** 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
* 힙에서의 부모 노드와 자식 노드의 관계
** 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
** 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
** 부모의 인덱스 = (자식의 인덱스) / 2
=== 삽입 ===
# 맨 마지막 노드에 새로운 데이터 추가 
# 부모 노드와 비교하여 아래에 해당하는 경우 교환
#* 최소 힙 인 경우 부모보다 신규 노드가 작다면
#* 최대 힙 인 경우 부모보다 신규 노드가 크다면
# 반복하여 부모 노드와 비교
# 루트 노드에 도달했거나 부모 노드가 더 작거나 같다면 멈춤

=== 삭제 ===
# 루트 노드를 반환
# 맨 마지막 노드를 루트 노드로 이동
# 두 자식 노드를 비교하여 아래에 해당하는 경우 루트 노드로 이동
#* 최소 힙 인 경우 더 작은 노드가 루트 노드보다 작다면
#* 최대 힙 인 경우 더 큰 노드가 루트 노드보다 크다면
# 반복하여 자식 노드와 비교
# 터미널 노드에 도달했거나 자식노드가 더 크거나 같다면 멈춤
@@ 1번째 줄: / 1번째 줄: @@
-[[분류:자료 구조]]
 ;Heap
 ;값을 노드 단위로 두고 노드들 가운데서 큰 값 또는 작은 값을 가지는 노드를 빠른 시간 내에 찾아내거나 정렬할 수 있도록 구성된 [[완전 이진 트리]]
-*<nowiki>;A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.</nowiki>
+* ;A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
-*키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.
+* 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.
-==Heap의 종류==
-*최대 힙(Max Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
-*최소 힙(Min Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
-==Heap의 연산 시간==
-*n개의 노드에 대해 구성 복잡도(삽입, 삭제 시간)은 O(logn)
-==Heap의 구현==
-*힙을 저장하는 표준적인 자료구조는 배열 이다.
-*구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
-*특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
-**예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
-*힙에서의 부모 노드와 자식 노드의 관계
-**왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
-**오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
-**부모의 인덱스 = (자식의 인덱스) / 2
-===삽입===
-#맨 마지막 노드에 새로운 데이터 추가
-#부모 노드와 비교하여 아래에 해당하는 경우 교환
-#*최소 힙 인 경우 부모보다 신규 노드가 작다면
-#*최대 힙 인 경우 부모보다 신규 노드가 크다면
-#반복하여 부모 노드와 비교
-#루트 노드에 도달했거나 부모 노드가 더 작거나 같다면 멈춤
-===삭제===
-#루트 노드를 반환
-#맨 마지막 노드를 루트 노드로 이동
-#두 자식 노드를 비교하여 아래에 해당하는 경우 루트 노드로 이동
-#*최소 힙 인 경우 더 작은 노드가 루트 노드보다 작다면
-#*최대 힙 인 경우 더 큰 노드가 루트 노드보다 크다면
-#반복하여 자식 노드와 비교
-#터미널 노드에 도달했거나 자식노드가 더 크거나 같다면 멈춤
-==[[힙 영역|메모리의 힙 영역]]==
+== Heap의 종류 ==
+* 최대 힙(Max Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
+* 최소 힙(Min Heap) : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
-*프로그램이 실행되면서 동적 할당용으로 사용되는 메모리 영역
+== Heap의 연산 시간 ==
-*프로그램이 실행될 때까지 알 수 없는 가변적인 양의 데이터를 저장하기 위해 프로그램의 프로세스가 사용할 수 있도록 예약되어 있는 메인 메모리의 영역
+* n개의 노드에 대해 구성 복잡도(삽입, 삭제 시간)은 O(logn)
-*프로그램들에 의해 할당되었다가 회수되는 작용이 되풀이됨
-*프로그램들이 요구하는 블록의 크기나 요구/횟수 순서에 일정한 규칙이 없음
-== 참고 문헌 ==
+== Heap의 구현 ==
+* 힙을 저장하는 표준적인 자료구조는 배열 이다.
+* 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
+* 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
+** 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
+* 힙에서의 부모 노드와 자식 노드의 관계
+** 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
+** 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
+** 부모의 인덱스 = (자식의 인덱스) / 2
+=== 삽입 ===
+# 맨 마지막 노드에 새로운 데이터 추가
+# 부모 노드와 비교하여 아래에 해당하는 경우 교환
+#* 최소 힙 인 경우 부모보다 신규 노드가 작다면
+#* 최대 힙 인 경우 부모보다 신규 노드가 크다면
+# 반복하여 부모 노드와 비교
+# 루트 노드에 도달했거나 부모 노드가 더 작거나 같다면 멈춤
-* 2020년도 국가공무원 9급 공채 필기시험 정보시스템 보안 8번 문제
+=== 삭제 ===
+# 루트 노드를 반환
+# 맨 마지막 노드를 루트 노드로 이동
+# 두 자식 노드를 비교하여 아래에 해당하는 경우 루트 노드로 이동
+#* 최소 힙 인 경우 더 작은 노드가 루트 노드보다 작다면
+#* 최대 힙 인 경우 더 큰 노드가 루트 노드보다 크다면
+# 반복하여 자식 노드와 비교
+# 터미널 노드에 도달했거나 자식노드가 더 크거나 같다면 멈춤