알고리즘
[2. 정렬] Heap Sort (1)
1. Heap이란? Heap은 heap property를 만족하는 complete binary tree이다. (1) complete binary tree binary tree는 자식 노드가 2개만 존재하며, 오른쪽 자식과 왼쪽 자식이 구분되는 tree이다. full binary tree: 모든 층(level)의 노드들이 꽉 차있는 형태 complete binary tree: 마지막 층(level)을 제외한 층의 노드들은 꽉 차 있으며, 마지막 층의 오른쪽부터 몇개의 노드가 비어있을 수 있음 (2) heap property 이 글에서는 max-heap property를 기준으로 다루고자 한다. max-heap property: 부모는 자식보다 크거나 같다 min-heap property: 부모는 자식보다 ..
