TIL
알고리즘 마라톤 진행도중 어쩔 수 없이 공부하는 알고리즘
heap (힙)
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리
힙을 알기 위해선 완전 이진트리의 구조에 대한 이해가 필요하다.
그런 의미에서 일단 완전 이진트리의 구조를 사알짝 보고가자.
8 level 0 [None, 8]
6 3 level 1 [None, 8, 6, 3]
4 2 5 level 2 [None, 8, 6, 3, 4, 2, 5]
=> [None, 8, 6, 3, 4, 2, 5]
의 구조를 갖는다.
이 때,
현재 인덱스(n)를 기준으로
왼쪽 자식의 인덱스는 2 * n
오른쪽 자식의 인덱스 2 * n + 1
를 갖고
부모의 인덱스는 n // 2
를 갖는다.
힙에서 중요하게 봐야할 점은 힙에 원소를 추가하는 것과, 힙에 원소를 제거하는 것 이다.
하나씩 살펴보도록 하자.
맥스 힙에 원소 추가
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
# 구현해보세요!
self.items.append(value)
i = len(self.items)-1
while i > 1 :
if self.items[i] > self.items[i//2]:
self.items[i],self.items[i//2] = self.items[i//2],self.items[i]
i = i //2
else:
break
max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items) 라고 구현을 하긴 했지만 설명을 덧붙이자면
해당 트리의 마지막에 임의의 값을 추가 했을 때, 해당 위치에서 부모 노드와 대소 비교를 통해 자리를 찾아가는 과정을 표현한 코드이다.
크기를 비교한 후a, b = b, a라는 손쉬운 방법으로 자리를 교체한다.
맥스 힙에 원소 제거
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1:
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
def delete(self):
n = len(self.items)-1
del_node = self.items[1]
if n > 2:
self.items[1], self.items[-1] = self.items[-1], self.items[1]
self.items = self.items[:-1]
j = 1
while n//2 > j:
if self.items[j*2] > self.items[j*2+1] and self.items[j*2] > self.items[j]:
self.items[j], self.items[j*2] = self.items[j*2], self.items[j]
elif self.items[j*2+1] > self.items[j*2] and self.items[j*2+1] > self.items[j]:
self.items[j], self.items[j*2+1] = self.items[j*2+1], self.items[j]
elif self.items[j] > self.items[j*2] and self.items[j] > self.items[j*2+1]:
break
j += 1
return del_node
max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items) # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete()) # 8
print(max_heap.items) # [None, 7, 6, 4, 2, 5]
라고 구현을 했지만 또 다시 설명을 덧붙이자면
독특하게도 인덱스 값을 이용해 제거하는 것이 아니라 최대값인 루트 노드를 빼와 제거한다. 루트노드와 맨 뒤에 있는 노드를a, b = b, a방식으로 교체하고.pop()으로 최대값을 끄집어낸다.
이 때 루트노드 자리로 들어간 자그마한 노드는 자식노드 중 더 큰 노드와 대소비교를 통해 자리를 교체해 가며 원래자리를 찾아간다.
단순히 자기 자리로 돌아가는 것이 아닌 전체적으로 트리를 정렬하는 셈.
여기까지 힙은 여기서 끝내고 본래 목적인 힙큐를 다뤄보겠다.
heapq
heapq는 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 내장 모듈
모든 부모 노드는 자식 노드보다 작거나 큰 이진트리 구조
내부적으로는 인덱스 0부터 n번째 원소가 항상 자식 원소(2n+1, 2n+2)보다 작거나 같은 최소 힙의 형태로 정렬
( 특이한점은 최소힙 방식으로 정렬한다는 점. )
heapq.heappush(heap, item):item을heap에 추가heapq.heappop(heap):heap에서 가장 작은 원소를pop & 리턴. 비어 있는 경우IndexError가 호출됨.heapq.heapify(x): 리스트x를 즉각적으로heap으로 변환함 ( in linear time, O(N) )
import heapq
heap = []
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 7)
heapq.heappush(heap, 2)
print(heap) # [1, 2, 7, 5]
heapq.heappop(heap)
print(heap) # [2, 5, 7]
a = [5, 9, 8, 4, 2]
heapq.heapify(a)
print(a) # [2, 4, 8, 5, 9]
작성한대로
import heapq를 통해 손쉽게 사용할 수 있다. 값을 추가하든 제거하든 알아서 정렬까지 해주기 때문에 활용하지 않으면바보라고 부르고 싶다.
2021.06.24
알고리즘 주차가 끝났다.. 그래도 알고리즘 공부는 계속됩니다
