힙 (자료 구조): 두 판 사이의 차이

'''힙'''(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 [[이진 트리|완전이진트리]](Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 heap힙 속성(property)을 만족한다.

* A가 B의 부모노드(parent node) 이면, A의 key값과키(key)값과 B의 key값키값 사이에는 일정한 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 key값이키값이 자식노드의 key값보다키값보다 항상 큰 힙을 '최대 힙', 부모노드의 key값이키값이 자식노드의 key값보다키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

key값의키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 그특히 외의형제 다른사이에는 노드들과는대소관계가 연관성을정해지지 찾아볼 수 없다않는다.

각 노드의 children 의자식노드의 최대개수는 heap 의힙의 종류에 따라 다르지만, 대부분의 경우는 children 의자식노드의 개수가 최대 2개인 [[이진 힙]](binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 [[우선순위 큐]]와 같은 추상적 자료형을 구현할 수 있다.

이진 힙(binary heap)은힙은 내부노드(internal node)에 키(key)와 요소(element)를 저장한 [[이진 트리]]로 다음과 같은 두 가지 특징을 갖는 것을 말한다.

힙 리스트(heap list)로 표현할 때 i번째 노드의 왼쪽 자식노드(left kindnode)의자식노드의 위치는 2i가 되며, i번째 노드의 오른쪽 자식노드(right kindnode)의자식노드의 위치는 2i+1이고, 또한 i번째 부노드의노드의 부모노드의 위치는 i/2가 된다.

다음의 내용의 테이블을배열을 최대힙으로 정렬해구성하는 본다과정을 보여준다.

이 테이블을배열을 사전 순으로순서에 따라 정렬(즉, A<B<C<…<Y<Z)한다면 힙으로 구성하는 과정은 다음과 같다.

T S R P H O A E //정렬끝힙 구성 끝.

이진 트리를 힙으로 구성하는 과정의 개략적인 의사코드는 아래와 같다.