반응형
힙 : 힙의 특성을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조
힙의 예시로 최소 힙이 있다. 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 된다.
주의할 점은 힙은 정렬된 구조가 아니다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐 좌우에 대한 관계는 정의하지 않는다.
<힙의 연산>
- 삽입
삽입에는 업힙(up heap)연산이 필요하고 과정은 다음과 같다. 삽입의 시간복잡도는 O(logN)이다.
1. 요소를 가장 하위레벨의 최대한 왼쪽으로 삽입
2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경
3. 계속해서 부모 값과 비교해 위치를 변경(가장 작은 값일 경우 루트까지 올라감)
- 추출
루트를 추출하면 되는 간단한 작업이지만 추출 이후 힙의 특성을 유지하는 작업이 필요하다.
그래서 시간복잡도는 O(logN)이다.
1.루트를 추출
2. 마지막 요소가 루트 자리로 올라감
3. 자식 노드와 값을 비교해서 자식보다 값이 크면 내려감(=다운힙 연산)
< 힙의 구현>
파이썬에서는 힙 모듈을 지원하기 때문에 쉽게 구현이 가능하다.
파이썬은 최소 힙만을 지원하지만 간단한 조작으로 최대 힙 역시 구현가능하다.
아래 예시를 보면 이해가 갈 것이다.
>>import heapq
>>heap = []
>>## add element , time complexity : O(logN)
>>heapq.heappush(heap, 3)
>>heapq.heappush(heap, 2)
>>heapq.heappush(heap, 4)
>>heapq.heappush(heap, 1)
## pop element, time complexity : O(logN)
>> for _ in range(4):
>> print(heapq.heappop(heap)
1
2
3
4
#######################################################
## list to heap
>>heap = [5,2,4,3]
>>heapq.heapify(heap)
>> for _ in range(4):
>> print(heapq.heappop(heap)
2
3
4
5
#######################################################
## max heap implement
>>nums = [5,8,7,6,9]
>>heap = []
>>for num in nums:
>> heapq.heappush(heap, (-num,num))
>>
>>while heap:
>> print(heapq.heappop(heap)[1])
9
8
7
6
5
** 참고 : 리스트로 구현한 힙의 삽입, 추출 연산
('파이썬 알고리즘 인터뷰' 책을 참고하였다.)
Class BinaryHeap(object):
def __init__(self):
self.items = [None]
def __len__(self):
return len(self.items)-1
###### insert #######
def _percolate_up(self):
i = len(self)
parent = i//2
while parent > 0:
if self.items[i] < self.items[parent]:
self.items[parent], self.items[i] = \
self.items[i], self.items[parent]
i = parent
parent = i //2
def insert(self, k):
self.items.append(k)
self._percolate_up()
###### extract #######
def _percolate_down(self, idx):
left = idx * 2
right = idx * 2 + 1
smallest = idx
if left <= len(self) and self.items[left] < self.items[smallest]:
smallest = left
if right <= len(self) and self.items[right] < self.items[smallest]:
smallest = right
if smallest != idx:
self.items[idx], self.items[smallest] = \
self.items[smallest], self.items[idx]
self._percolate_down(smallest)
def extract(self):
extracted = self.items[1]
self.itmes[1] = self.itmes[len(self)]
self.items.pop()
self._percolate_down(1)
return extracted
댓글