코딩테스트 - tree, heap

이번에는 자료구조 중에서 heap에 대해서 글을 써보려 한다. 그리고 heapq라는 python 라이브러리(모듈)에 대해서도 조금 써보려 한다. 사실 나는 heap이라는 것을 사용해본 경험이 아예 없다 공부를 좀 해보니 트리에 대해서도 설명해주면 좋을 것 같아서 트리와 같이 설명하려 한다.

1. tree
   tree란, 노드와 간선으로 이루어진 자료구조인 그래프의 한 종류이다. tree는 두 개의 노드사이에는 반드시 하나의 간선만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 각각의 노드 간에부모와 자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.

2. heap
   heap이란, 데이터에서 최댓값과 최솟값을 빠르게 찾기위해 고완된 완전 이진 트리(Complete Binary Tree라고 한다. 최솟값(최댓값)을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸리지만 heap을 사용하면 O(logn)만큼 소요되서 빠르게 구할 수 있다고 한다. 최대힙과 최소힙으로 나뉘어지며, 최대힙은 부모노드의 값이 자식노드보다 큰 경우, 최소힙은 부모노드의 값이 자식노드보다 작은 경우이다.

• 완전 이진 트리 : Complete Binary Tree
  이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다. 즉, 왼쪽이 비어있고 오른쪽이 채워져 있으면 완전이진트리가 아닌 것이다.

• 이진트리
  자식 노드가 둘 이하인 트리를 말한다.

이미지의 왼쪽이 완전이진트리가 맞고, 오른쪽은 완전이진트리가 아니다.

3. 관련 함수

heapq.heappush(heap, item) : item을 heap에 추가
heapq.heappop(heap)        : heap에서 가장 작은 원소를 리턴하고 제거. 비어 있는 경우 IndexError가 호출됨. 
heapq.heapify(list)        : 리스트를 즉각적으로 heap으로 변환함