[c++] 알고리즘 개념공부 :: 자료구조 - 힙

힙

1. 용도

2. 구현

3. 종류

4. 연산

5. 정렬

 

힙

힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다.

partial-ordering (부분 정렬)을 만족하는 left-complete binary tree (좌측 완전 이진 트리) 이다.

부분 정렬을 만족한다는 말은 '부모 노드와 자식노드' 간에는 특정 대소관계 성립하지만, '형제노드'간에는 해당 대소관계가 성립하지 않는다는 뜻이다.

이진 탐색 트리에서는 중복된 값을 허용하지 않지만 힙 트리에서는 허용한다.

 

용도

 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. 배열과 연결리스트를 이용하면 삽입과 삭제 연산 중 하나가 O(n)일 수 밖에 없다. 하지만 힙을 이용하면 가장 큰 값이나 가장 작은 값을 둘 다 O(logn)만에 빠르게 찾을 수 있다.

이와 같은 특성 때문에 힙 정렬이라는 정렬 알고리즘에서도 쓰인다.

 

구현

힙은 배열, 연결리스트 이렇게 2가지 방법으로 구현할 수 있다. 트리 구현과 비슷하게 대부분 배열을 사용한다. 자세한 구현 내용은 이진 트리에서의 구현과 같다.

 

종류

• 최대 힙

• 최소 힙

  최대 힙은 부모 노드가 자식 노드보다 큰, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 partial ordering이 성립한다. total ordering은 만족하지 않아도 된다.

 

연산

• 삽입

  삽입 연산 시 가장 말단(마지막 index)에 삽입한 후 부모 노드들과 순차적으로 레벨을 올라가면서 비교/교환해서 힙의 성질을 만족하도록 수정한다.

  힙의 높이는 완전 이진 트리이므로 logn이다. 따라서 삽입 연산의 복잡도는 O(logn)이다.

• 삭제

  힙에서의 삭제 연산은 루트 노드를 제거하는 것이다. 루트 노드 삭제 후 빈 자리에 가장 말단 노드를 채운 후 자식 노드들과 순차적으로 레벨을 내려가면서 비교/교환해서 leaf node까지 내려간다.

  삭제 연산 또한 힙의 높이에 비례하므로 복잡도가 O(logn)이다.

 

정렬

 힙을 통해서 어떤 데이터를 정렬하려면 힙 자료구조를 만족하게 구성하고, 루트 노드에서 요소들을 하나씩 삭제해가면서 다시 힙 구조로 만드는 걸 반복하면 된다.

 이 때, 데이터의 갯수만큼 이 과정을 반복하고, 이 과정의 시간복잡도가 위에서 설명했듯이 O(logn)이므로, 전체 시간복잡도는 O(nlong)이다.