자료구조의 보석 힙(Heap)

2010-02-19 19:27:20

오늘은 자료 구조의 보석인 힙(Heap)을 찾아서 가기로 해요..

   

태고의 도시 야율론에 힙이라는 보물이 숨겨져 있다는 보물지도를 얻은 이비는 친구인 리시타와 피오나와 함께 야율론으로 떠나는 배를 탑니다.

   

이 보물지도는 고대 문자인 에리스문으로 되어 있는데, 이것을 해석하는 것은 아주 어렵다고 합니다.  특히 다중상속문이 존재하는 이 언어는, 고도의 지식을 요합니다.  더구나 템플릿을 이용하기도 하는데, 이 템플릿은 스택, 큐, 동적 배열을 한단어로 표현할 수 있을 정도로 강력한 마법 언어로 알려져 왔습니다.

   

다행히 이 보물지도에 있는 에리스문은 상속도 없고 템플릿도 없습니다.

   

리시타와 피오나 모두 준비가 되었다고 하는군요.  선장인 이비가 출발을 외칩니다..~

   

뿌웅..~~~

   

   

리시타 : 누구야.. 방구 뀐게!!!!

피오나 : 난 아냐.. 이비야 이비..

   

드디어 야율론에 도착한 이들.. 이들은 힙을 찾아 험난한 모험을 하게 됩니다...

   

.....

<중략>

   

드디어 찾은 힙...

그런데 힙은 어느새 변형이 되어 있었죠.  힙정렬을 만들려고 했었던 이들이 찾은 힙의 모습은 우선순위 큐였던 것입니다.

허탈한 세명..

이들은 태고의 모습이었던 힙정렬의 힙을 언젠가는 찾겠다고 하면서 하루를 또 마감합니다.

   

힙을 이용한 우선순위 큐는, 수학 도구에서 많이 사용하는 프림, 다익스트라, A* 알고리즘에서 만이 사용하죠.

일반적으로 복잡한 구조이기 때문에 힙을 사용하지 않고, 그냥 O(n) 알고리즘인 검색을 이용하기도 합니다.

   

우선순위 큐에 대한 모습은 다음과 같습니다.

   

   

다분히 추상적인 형태로만 만들어진 이 우선순위 큐는.. 실제 사용하기 위해서는 조금 다듬어져야 됩니다.

Put 은 데이터를 하나 추가하는 것이고, Get은 데이터를 하나 가져오는 것입니다.

힙의 특성상 Swap 기능이 필요하므로 Swap 함수를 보이지 않게 살짝 숨겼습니다.

Heapify는 자식들이 힙을 이루는 경우, 부모로부터 힙을 만들 수 있는 구조가 되어 있습니다.

   

한번 Heapify 함수를 보도록 할까요?

   

Heapify 함수는 자식(left, right)들 중에 높은 순위(여기서는 작은 값)를 가지고 있는 애를 선택해서 부모와 자식의 값을 교환합니다.

그런 후 교환된 자식에 대해서 Heapify를 재귀적으로 호출하게 됩니다.

   

다음으로 Put & Get 함수입니다.

   

   

Put 함수에서는 맨 마지막에 새로운 원소를 추가하고, 부모와의 값 비교를 재귀적으로 하여, 자신의 위치를 찾아갑니다.

Get 함수에서는 가장 작은 값(가장 높은 순위)인 루트로부터 데이터를 가져오고, 루트와 맨 마지막 값을 바꾼 후, 힙으로 만듭니다.

   

다음으로는 Update 함수입니다.  Dijkstra 알고리즘이나 A* 알고리즘에서는 정점값(Vertex value)이 바뀌는 경우가 발생하는데, 이 때 사용하는 것이 바로 Update 함수입니다.

   

   

update 함수에서는 일반화했습니다.  일반적으로는 더 작은 값으로만 가기 때문에 Upward 경로만 만들어도 무난합니다.  즉 Heapify(h); 부분을 빼도 무방합니다.  이 함수는 사실 Put 함수와 동일한 로직이기 때문에 Put 함수에서 Update 함수를 호출해도 무방합니다.  (단 Upward path만 있다는 가정이 있어야 하겠죠)

   

이비와 리시타와 피오나는.. 야율론에서 찾은 이 힙이 잘 동작하는지 검사하기 위해서 에리스문으로 이 힙을 테스트할 수 있도록 마법의 문자를 적었습니다.  결과는 대 성공.. 그들은 이 도구를 A* 를 이용한 퍼즐 맞추기에 사용하기로 결심하고.. 다음을 기약하기로 했습니다.