힙Heap 이란?

저번 시간에 우선순위 큐를 자료구조별로 구현할 때의 장단점을 보았다. 특히 균형 이진 검색 트리로 구현한다면 가장 안정적이면서 빠른 $O(logn)$ 복잡도로 삽입과 삭제가 이루어지는 것을 보았다. 그런데 이진 힙을 통해 구현하면검색, 삽입, 삭제에는 $O(logn)$의 복잡도를 가지지만, 최소/최대 값 찾기에는 $O(1)$의 복잡도를 가질 수 있다고 한다. (자주 현재 상황을 확인해야 하는 경우에 자주 사용될것이라는 걸 알 수 있다.)

힙의 속성

트리와 비슷하다. (몇 가지 속성을 가지는 트리이다.) 그리고 사용되는 거의 모든 힙은 이진 힙 binary heap이므로 이진 힙을 기준으로 살펴본다.

• 힙의 기본 요구사항은 노드의 값이 그 자식 노드 '이상' 혹은 '이하'여야 한다. (힙 속성)
  • MIn Heap : 노드의 값이 자식 노드의 값보다 작거나 같아(이하)야만 한다.
  • Max Heap : 노드의 값이 자식 노드의 값보다 크거나 같아(이상)야만 한다.
• 트리의 높이 h가 있을때, 모든 리프 노드들이 h혹은 h-1 레벨에 있어야한다. (즉 '완전complete 이진 트리'여야 한다.)

구현

트리와 달리 배열을 사용해서, 즉 포인터 없이 인덱스만 사용해 구현할 수 있다. 루트부터 시작해서 각 레벨별로 순서대로 배열에 위치시킨다.

      17
  13        6
1    4   2    5

이걸 배열에 담으면 [17, 13, 6, 1, 4, 2, 5] 이 된다.

부모, 자식 노드 찾기

어떤 노드의 인덱스 i를 가지고 부모, 자식 노드의 인덱스를 찾을 수 있다. 부모 : (i-1)/2 자식 : (i*2)+1, (i*2)+2

6노드의 인덱스 2로 직접 구해보자. (2-1)/2=0이므로 0번째 노드인 17이 부모가 맞고, (2*2)+1=5, (2*2)+2=6이므로 5,6번째 노드인 2와 5가 자식이 맞다.

삭제

Percolate Down(흘러내리기) 방식이라고 부른다.

모든 우선순위 힙은 루트 노드만 제거한다. 그리고 가장 마지막 노드를 루트 자리에 넣고. (힙 조건을 위배하게 된다.) 그 후에 percolate down 방식으로 힙으로 만들어준다. 루트 노드의 왼쪽과 오른쪽 자식을 비교한다. 조건에 맞지 않는 경우 부모와 해당 자식의 위치를 바꾼다. 그렇게 리프 노드까지

삽입

거꾸로 percolate up 방식이라고 한다. 일단 맨 마지막 노드에 새로운 노드를 추가하고 부모와 비교해봐서 조건에 맞으면 그대로 넘어가지만, 조건에 맞지 않는 경우 계속 부모와 바꿔준다.