(이진) 힙 자료 구조는 완전 이진 트리로 볼 수 있는 배열 객체다. 트리의 각 노드는 배열에서 그 노드의 값을 저장하는 원소와 대응한다. 이 트리는 가장 낮은 층을 빼고는 완전히 차 있고, 가장 낮은 층은 왼쪽부터 채운다. 힙을 나타내는 배열 A는 두 가지 인자를 갖는다. 배열 A에 있는 원소의 개수를 나타내는 length[A]와 배열 A의 원소 중 힙에 속하는 원소의 개수를 나타내는 heap-size[A]다. 그리고 heap-size[A] ≤ length[A]다. 다시 말해서 A[1..length[A]]에 있는 값들이 다 유용할 수는 있지만, A[heap-size[A]] 뒤에 있는 것들은 힙의 원소가 아니다. 트리의 루트는 A[1]이다. 그리고 노드의 인덱스 i가 주어지면 부모 Parent(i), 왼쪽 자식 Left(i), 오른쪽 자식 Right(i)는 다음과 같이 간단히 구할 수 있다.
Parent(i)
return [i / 2]
Left(i)
return 2i
Right(i)
return 2i + 1
대부분의 컴퓨터에서 Left 프로시저는 i의 이진 표현을 왼쪽으로 한 비트 이동시키는 연산 하나로 2i를 간단하게 계산할 수 있다. 비슷하게 Right 프로시저는 i의 이진 표현을 왼쪽으로 한 비트 이동시킨 다음 최하위 비트에 1을 더함으로써 2i + 1을 빠르게 계산할 수 있다. Parent 프로시저는 i를 오른쪽으로 한 비트 이동시켜서 [i / 2]을 계산할 수 있다. 힙 정렬을 잘 구현한 프로그램에서는 이 세 프로시저를 '매크로'나 '인라인' 프로시저로 구현하는 경우가 많다.
이진 힙에는 최대힙과 최소힙 두 가지가 있다. 두 가지 모두 노드의 값은 힙 특성을 만족시킨다. 힙 특성은 힙의 종류에 따라 다르다. 최대힙에서 최대힙의 특성은 루트 노드를 제외한 모든 노드 i에 대해서
A[Parent(i)] ≥ A[i]
가 된다. 즉, 임의의 노드의 값은 그 부모의 값보다 클 수 없다. 그러므로 최대 힙에서 가장 큰 값은 루트에 저장되고, 서브 트리는 자신의 루트보다 크지 않은 값을 갖는다. 최소힙은 정반대 방법으로 구성된다. 그리고 최소힙의 특성은 루트 노드를 제외한 모든 노드 i에 대해
A[Parent(i)] ≤ A[i]
가 된다. 즉, 최소힙에서 최소값은 루트에 있다. 힙 정렬 알고리즘에서는 최대힙을 사용하며, 최소힙은 우선순위 큐에서 사용한다.
힙을 트리로 보는 관점에서 노드의 높이를 그 노드에서 리프(Leaf)에 이르는 하향 경로 중 가장 긴 것의 간선 수로 정의한다. 그리고 힙의 높이는 루트의 높이로 한다. 힙은 완전 이진 트리를 기반으로 하고 있기 때문에 원소 개수가 n인 힙의 높이는 Θ(log(n))이다. 힙에 대한 기본 연산의 수행 시간은 오래 걸려도 트리의 높이에 비례하는 정도이기 때문에 Ο(log(n))이다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithm Second Edition, The MIT Press
문병로, 심규석, 이충세 역, Introduction to Algorithm Second Edition, 한빛미디어
Parent(i)
return [i / 2]
Left(i)
return 2i
Right(i)
return 2i + 1
대부분의 컴퓨터에서 Left 프로시저는 i의 이진 표현을 왼쪽으로 한 비트 이동시키는 연산 하나로 2i를 간단하게 계산할 수 있다. 비슷하게 Right 프로시저는 i의 이진 표현을 왼쪽으로 한 비트 이동시킨 다음 최하위 비트에 1을 더함으로써 2i + 1을 빠르게 계산할 수 있다. Parent 프로시저는 i를 오른쪽으로 한 비트 이동시켜서 [i / 2]을 계산할 수 있다. 힙 정렬을 잘 구현한 프로그램에서는 이 세 프로시저를 '매크로'나 '인라인' 프로시저로 구현하는 경우가 많다.
이진 힙에는 최대힙과 최소힙 두 가지가 있다. 두 가지 모두 노드의 값은 힙 특성을 만족시킨다. 힙 특성은 힙의 종류에 따라 다르다. 최대힙에서 최대힙의 특성은 루트 노드를 제외한 모든 노드 i에 대해서
A[Parent(i)] ≥ A[i]
가 된다. 즉, 임의의 노드의 값은 그 부모의 값보다 클 수 없다. 그러므로 최대 힙에서 가장 큰 값은 루트에 저장되고, 서브 트리는 자신의 루트보다 크지 않은 값을 갖는다. 최소힙은 정반대 방법으로 구성된다. 그리고 최소힙의 특성은 루트 노드를 제외한 모든 노드 i에 대해
A[Parent(i)] ≤ A[i]
가 된다. 즉, 최소힙에서 최소값은 루트에 있다. 힙 정렬 알고리즘에서는 최대힙을 사용하며, 최소힙은 우선순위 큐에서 사용한다.
힙을 트리로 보는 관점에서 노드의 높이를 그 노드에서 리프(Leaf)에 이르는 하향 경로 중 가장 긴 것의 간선 수로 정의한다. 그리고 힙의 높이는 루트의 높이로 한다. 힙은 완전 이진 트리를 기반으로 하고 있기 때문에 원소 개수가 n인 힙의 높이는 Θ(log(n))이다. 힙에 대한 기본 연산의 수행 시간은 오래 걸려도 트리의 높이에 비례하는 정도이기 때문에 Ο(log(n))이다.
Reference
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithm Second Edition, The MIT Press
문병로, 심규석, 이충세 역, Introduction to Algorithm Second Edition, 한빛미디어