힙과 우선순위 큐도 별로 어렵진 않다.

물론 깊이 들어가면 어려운건 매 한가지지만.

어쨌거나 기본적인 개념은 어려운것이 아니니...


힙(Heap)

위키피디아의 정의에 따르면,

힙이란 힙 속성(heap property)를 만족하는 특별한 트리 기반의 자료 구조란다.

힙 속성(heap property)란?

만약 B 가 A 의 자식 노드라면, key(A) >= key(B)를 만족하는 것이다.

좀 더 쉽게 말하면 가장 큰 값을 가지는 노트가 항상 Root 가 되는 것이다.

File:Max-Heap.svg

( Author:  Ermishin, http://en.wikipedia.org/wiki/File:Max-Heap.svg )

위 그림과 같은 예가 힙이다.


힙은 모든 항목들이 정렬되는 것이 목표가 아니라, 가장 크거나 작은 항목만 빨리 찾을 때 좋은 자료 구조이다.


힙은 왼쪽 평형을 이루기 때문에 노드가 추가 될 때, 트리는 단계별로 왼쪽부터 채워진다.

그리고 이런 힙을 표현하는 좋은 방법은 배열에 저장하는 것이다.

왼쪽 평형을 이루는 트리를 배열에 저장할 때의 장점은

힙의 마지막 노드의 위치를 빨리 알 수 있게 되는것이다.

( 힙에서 데이터를 삽입 할 때, 삽입 위치는 마지막 노드의 다음 노드에 삽입한 후,

연산을 시작하기 때문에 이것은 중요하다. )

또한 i 번째 노드의 부모의 위치는 floor((i-1)/2),

자식의 위치는 2i+1, 2i+2 로 찾기 쉬운 장점도 있다.

 

힙의 인터페이스는 insert 와 extract 정도...

임의의 data 를 delete 하는 인터페이스는 없다.


우선순위 큐(Priority Queue)

우선순위 큐는 힙과 동일하다. 그리고 힙의 인터페이스를 그대로 사용하면 된다.

거기에 peek 인터페이스만 추가하면 된다.



힙의 변종들(Variants)

위키피디아에는 여러 힙의 변종들이 있는데...

역시나 그 힙들의 각각이 특징을 다 외우지는 못하겠다.

http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants

위 링크에 보면 여러 힙들의 Time Complexities 가 표로 작성되어 있는데,

큰 데이터를 다뤄야 하는 경우라면, 상황에 따라서 가장 중요한 연산의 복잡도를 고려하여

여러 힙 중에서 적절한 것을 고르면 되겠다.



기타

자료 집합을 힙으로 만들 때,

모든 원소에 대해서 heap_insert() 를 하게 되면 O(n lg n) 의 복잡도를 가지게 된다.

이것을 O(n) 의 복잡도로 실행할 수 있다.

루트의 위치가 floor(n/2)-1 에서 0까지인 트리를 힙으로 계속 만들어 가면 된다고 한다.

( 사실 무슨 말인지 모르겠다. 실제 예제를 가지고 확인해 보면 좋겠다 )

이렇게 되면 O(lg n)시간에 실행되는 floor(n/2)-1 개의 연산이 있지만,

힙 만드는 과정의 절반만이 두 단계 이상의 자료 비교를 필요로 하므로 전체적인 실행시간은

O(n) 이 된다고 한다.


(2012.7.4 추가)

자료 집합을 힙으로 만들 때, O(n) 시간에 해결하는 방법은...

마지막 노드를 가지고 있는 부모 노드로 부터 - Root 의 인덱스가 0 일 때, floor(n/2)-1 번 위치부터

Root 로 가면서 Heapfy 하는 것이다.

처음에는 원소가 2개 혹은 3개를 가진 트리 형태를 전부 Heapfy 하고,

그 윗 단계로 가게 되면, extract 이후에 Reheapfy 하는 과정..

즉, Root 와 그 자식들을 비교해서 Heapfy 하는 과정을 계속 반복하는 것이다.



결론

기본 힙은 쉬운거 같다.

근데 힙의 Variants 들도 참 많다.

각 Variants 들의 특징도 한번씩 살펴보면 좋겠지만.. 시간이 될까?

반응형

설정

트랙백

댓글