9. 힙 정렬
알고리즘 공부
2019. 9. 27.
힙 트리란? 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리의 형태를 띄고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap), 작아야(Min heap)하는 규칙이 있다. 따라서 루트 노드에는 항상 데이터들 중 가장 큰 값(혹 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹 최솟값)을 O(1)안에 찾을 수 있다. 단순히 최댓값(최솟값)을 O(1)안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요는 없다. 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용한다. 달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문이다..
