[자료구조] 힙

[자료구조] 힙

우선순위 큐 (Priority Queue)

• 큐의 핵심 연산인 큐에 데이터를 삽입하는 행위와 큐에서 데이터를 꺼내는 행위는 동일하다.
• 다른 점은 큐는 먼저 들어간 데이터가 먼저 나오지만(First in First out) 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

우선순위 큐 구현 방법 - 1. 배열을 기반으로 구현

• 배열을 이용하여 구현하게 될 경우, 우선순위가 높을수록 배열의 앞쪽 데이터에 위치 시킨다. 이렇게 되면 데이터를 반환하는 연산은 쉽게 접근할 수 있다.
• 단점은 데이터를 삽입할 때 삽입의 위치를 찾기위해 배열에 저장된 모든 데이터와 값을 비교해야 한다.
• 또 다른 단점으로 데이터를 삽입 및 삭제하기 위해 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다.

우선순위 큐 구현 방법 - 2. 연결리스트를 기반으로 구현

• 연결리스트로 구현할 경우 데이터를 삽입 및 삭제하기 위해 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 할 필요는 없다.
• 하지만 데이터를 삽입할 때 삽입의 위치를 찾기위해 리스트에 저장된 모든 데이터와 값을 비교해야 하는 단점은 여전히 존재한다.

우선순위 큐 구현 방법 - 3. 힙(Heap)

• 배열을 기반으로 우선순위 큐를 구현하는 방법과 연결리스트를 기반으로 구현하는 방법은 위와 같은 단점이 존재하기 때문에 힙이라는 자료구조를 사용한다.

힙(Heap)

• 힙은 완전이진트리이다. 또한 최대 힙의 경우는 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 하고, 최소 힙의 경우 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 한다.

힙의 데이터 저장 과정

• 새로운 데이터는 우선 순위가 제일 낮다는 가정하에 완전이진트리의 마지막 노드 다음 노드에 저장한다. 그 후, 부모 노드와 우선순위를 비교하며 제 위치를 찾을 때까지 반복한다. 최대 트리의 높이만큼 반복하게 되므로 시간복잡도는 o(logn) 이 된다.

힙의 데이터 삭제 과정

• 무조건 루트 노드를 삭제한 후, 트리를 제 모양으로 만들어 준다. 루트를 삭제한 후, 마지막 노드를 루트 노드의 자리로 옮긴 후 우선순위가 높은 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.
• 역시 최악의 경우 트리의 높이만큼 반복하며 비교하게 되므로 O(logn)이 된다.

삽입과 삭제 과정에서 보이는 성능 평가

• 배열 기반 삽입 시간 복잡도 O(n) / 배열 기반 삭제 시간 복잡도 O(1)
• 리스트 기반 데이터 저장 시간 복잡도 O(n) / 리스트 기반 데이터 삭제 시간 복잡도 O(1)
• 힙 기반 데이터 저장 시간 복잡도 O(lgn) / 힙 기반 데이터 저장 시간 복잡도 O(lgn)

힙 구현을 위해서 필요한 자료구조

• 배열을 기반으로 구현한다. 리스트를 기반으로 힙을 구현하게 되면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 번거롭다.
• 배열을 기반으로 구현하기 위한 규칙은 왼쪽 자식 노드의 인덱스 값은 부모노드의 인덱스 값 *2 / 오른쪽 자식 노드의 인덱스 값은 부모노드의 인덱스 값 * 2 + 1 / 부모 노드의 인덱스 값은 자식 노드의 인덱스 값 / 2

n개의 데이터를 이용하여 힙을 만드는데 걸리는 시간 복잡도

• n개의 데이터를 하나씩 힙에 삽입하여 힙을 구현한다고 하자.
• 첫번째 데이터를 삽입하면 트리에 아무것도 없으니 lg1 + c 의 시간이 걸린다.
• 두번째 데이터를 삽입하면 lg2 + c의 시간이 걸린다.
• n번째 데이터를 삽입하면 lgn + c의 시간이 걸린다.
• 즉, n개의 데이터를 삽입하는데 걸리는 시간은 lg1 + lg2 + lg3 + … + lgn + c가 된다.
• logaX(a가 밑 x가 진수) 를 1~n 구간에 대해 적분하면 [xlgx - x/lna + c] 1~n 이 되므로, 최고차항만 빅오에 넣게 되면 O(nlgn)이 된다.