이 문제는 힙 자료구조 바로 뒤에 나오는 문제여서 힙정렬을 이용해여 풀었더니 바로 풀려서..문제에 대한 정리보다 힙 자료구조에 대한 정리를 해야겠다.
힙은 트리를 사용하는 자료구조써 힙 정렬을 위해 탄생 한 자료구조이나 힙 정렬뿐만 아니라 우선순위 큐, 다익스트라 알고리즘 등..여러군데에 쓰이고 있다.
힙이라하면 부모 노드의 값이 자식노드의 값보다 작은 최소힙을 의미하며 그 반대로 부모노드의 값이 자식노드의 값보다 큰 최대힙 또한 만들 수 있다.
힙 자료구조는 오로지 수직적으로 부모와 자식노드간 대소관계만 고려한다. 트리구조를 사용하는 다른 고리즘 BST는 노드간 왼쪽, 오른쪽 좌우 노드의 대소관계를 고려한다.
힙은 보통 배열로 구현이 되며 선택사항이지만 구현의 용이성을 위해 배열의 첫번째요소 (0번째 인덱스)는 사용하지 않으며 1번 인덱스부터 사용한다.
힙은 힙에 삽입, 추출하는 연산을 가지고 있다. 그리고 삽입과 추출시에 항상 힙 자료구조를 유지하기 위해 수행되는 부가적인 2가지의 연산들이 있다.
먼저 삽입연산부터 살펴보자.
힙은 배열로 구현되어있는데 힙을 트리모양으로 구현하면 위와 같다.
배열의 마지막 요소에 원소를 삽입하고 힙 자료구조를 유지하는 연산을 실시한다. 부모의 인덱스는 자식 인덱스의 / 2이다. 그래서 자식과 부모요소를 비교해나가며 제자리를 찾을때 까지 계속 반복한다.
추출연산
추출은 항상 맨 앞 원소, 배열의 원소로 따지면 1번인덱스 (0번은 사용안한다고 했으므로 )가 추출된다. 그러나 2,3...n번인덱스가 오름차순으로 정렬되있을거라는 보장은 없다.
원소를 추출하고 힙 자료구조를 유지하기 위해 가장 마지막 인덱스원소를 루트로 올린 후 자식 원소와 비교하며 최소힙의 경우 자기가 자식노드보다 크다면 자식노드와 자신의 위치를 바꾼다 그리고 제자리를 찾을때까지 반복한다. 이때 구현은 재귀로 한다.
파이썬 알고리즘 인터뷰에 나와있는 코드를 바탕으로 힙의 구현 정리
class BinaryHeap:
def __init__(self):
self.items = [None]
def __len__(self):
return len(self.items)-1
def _percolate_up(self):
i = len(self)
parent = i // 2
while parent > 0:
if self.items[i] < self.items[parent]:
self.items[i],self.items[parent] = self.items[parent], self.items[i]
i = parent
parent = parent // 2
def insert(self,k):
self.items.append(k)
self._percolate_up()
def _percolate_down(self,idx):
left = idx * 2
right = idx * 2 + 1
smallest = idx
if self.items[left] <= len(self) and self.items[left] < self.items[smallest]:
smallest = left
if self.items[right] <= len(self) and self.items[right] < self.items[smallest]:
smallest = right
if smallest != idx:
self.items[smallest], self.items[idx] = self.items[idx], self.items[smallest]
self._percolate_down(smallest)
def extract(self):
extracted = self.items[1]
self.itemsi[1] = self.items[len(self)]
self.items.pop()
self._percolate_down(1)
return extracted
문제가 되면 삭제하겠습니다.
