[자료구조] 힙

힙

힙은 트리의 일종이다.

• 단, 힙은 완전 이진트리여야만 한다.(형태 속성, 모든 노드가 2개의 자식을 갖고, 마지막 레벨에서만 왼쪽에서 오른쪽으로 노드가 순차적으로 채워져 있음) 따라서 노드의 개수가 n일 때힙의 높이는lg(n)이고, 리스트로 트리를 표현할 수 있다.
• 그리고 모든 노드의 데이터는 자식 노드의 데이터보다 크거나 같아야 한다. (힙 속성)

힙정렬

• 이러한 힙을 사용해서 데이터를 정렬할 수도 있는데, 이를 '힙정렬' 이라고 부른다. 힙은 일종의 완전 이진트리이므로, 리스트로 표현이 가능하다.(트리파트 참고) 이 말은 즉, 리스트를 힙으로 표현할 수도 있다는 것이다.
• 다만 힙은 부모노드의 데이터가 자식 노드의 데이터보다 커야 하므로, 이 조건을 만족시켜야 한다. 그렇지 않은 리스트를 힙 조건에 맞게 바꿔주는 것을 heapify라고 한다.
• 이 heapify과정으로 '하나의 노드'를 힙에 적합하도록 변경하는데 걸리는 시간복잡도는 최악의 경우 트리의 높이만큼 수정의 작업이 필요하므로, O(lg(n))이다.

heapify 시간 복잡도

• 그렇다면 리스트의 전체를 힙에 적합하도록 변경하는데 걸리는 시간 복잡도는 얼마나 될까?
• 노드의 개수는 n개이고 이 모두가 heapify과정을 겪어야하므로 O(lg(n)*n) = O(lg(n) n)이 될 것이다.

힙정렬의 수행과정

• 그런데 이렇게 모두에 heapify를 적용했다고 해도 이 트리의 리스트가 정렬되진 않는다.
• 그렇다면 앞서 언급한 '힙정렬'은 어떻게 수행하는 것일까?

1) 가장 먼저 리스트를 힙의 형태로 갖춘다(리스트 전체를 힙에 적합하도록 변경)

2) 마지막 노드와 root노드(숫자가 가장 큰 노드)의 데이터를 변경한다.

3) 마지막 노드는 없는 취급 한다 (자연스럽게 마지막 노드에는 가장 큰 숫자가 위치한다.)
4) root노드에 heapify를 걸어 적절한 위치를 찾아준다. (이 과정에서 없는 취급된 노드의 숫자를 제외하고 현재 트리에서 가장 큰 숫자가 root 노드에 위치하게 될 것이다.)

5) root노드만 남을 때까지 2~4의 과정을 반복한다 (heapify를 하는 것에서 멈춰야함)

• 이 과정을 마치면 리스트가 정렬된다. 힙정렬의 시간복잡도는 리스트 전체를 힙의 형태로 만드는 데에 걸리는 시간 O(lg(n)n) + 리스트 끝에서부터 데이터변경 (O(1))과 heapify를 n번 수행 O(lg(n)n) + 1) = O(lg(n)n). 따라서
• O(2lg(n)n) = O(lg(n)n)이므로 최종적인 시간복잡도는 O(lg(n)n) 이다.
• cf. 원래의 힙속성은 부모의 데이터는 자식의 데이터보다 크기 때문에 오름차순으로 정렬되지만 내림차순으로 정렬하고 싶으면 힙 속성을 부모의 데이터가 자식의 데이터보다 작도록 설정하면 된다.

힙 데이터 삽입

• 힙에 데이터를 삽입할 때는

1) 리스트의 가장 끝(힙의 가장 끝)에 해당 데이터를 저장하고
2) 그의 부모노드를 heapify해가는 형식으로 힙조건을 만족시킨다. (부모노드의 데이터가 더 작을 경우 swap)

• 시간복잡도는 힙의 끝에 데이터 저장 O(1) + 최악의 경우 부모와 데이터교환 lg(n)회
• 따라서 힙 데이터 삽입의 시간복잡도는 O(lg(n))이다.

힙의 활용 : 우선순위 큐

• 힙은 우선순위 큐라는 추상 자료형을 구현하는 데에도 사용된다.
• 우선순위 큐는 큐에 우선순위 개념을 더한 것이다. 큐는 단순히 먼저 들어간 데이터가 먼저 나왔지만, 우선순위 큐는 별도의 우선순위 개념이 존재한다. (예를 들어 큰 데이터먼저 나오도록 설정할 수 있다.)

우선순위 큐

• 큰 데이터가 먼저 추출되는 우선순위 큐의 노드 데이터를 추출하려면

1) 가장 큰 데이터는 root노드에 있으므로, root노드와 마지막 노드의 데이터를 바꾼다.

2) 그 후 마지막 노드의 데이터를 변수에 저장해두고 마지막노드는 삭제한다.

3) 마지막으로 원래 힙의 속성을 지키기 위해 root노드에 heapify를 걸어준다.

4) 변수에 저장해둔 데이터를 리턴한다.

• 의 과정을 수행한다. 시간복잡도는 데이터 교환 O(1) + 마지막 노드의 데이터를 변수에 저장 O(1) + 힙속성 유지를 위한 heapify O(lg(n)).
• 따라서 데이터 추출은 O(lg(n) + 2) = O(lg(n))의 시간복잡도를 가진다.

---

cf. 동적배열이나 링크드 리스트로도 우선순위 큐를 구현할 수 있다. 다만 이 둘은 삽입하고 정렬하는데에 시간이 오래걸린다. (O(n))

그렇지만 추출하기는 쉽다는 장점이 존재한다. (O(1))