힙정렬1 5. Sorting Algorithm ㅣ힙 그리고 힙(heap)정렬 알고리즘 힙(heap) 자료구조란? 힙(heap)은 1차원 배열 중에서 저장된 값이 힙 조건(모양 + 값 조건)을 만족하는 리스트(배열)를 의미한다. (실제 데이터 값은 리스트에 저장되어 있고 리스트의 값이 표현하는 (가상의) 이진트리가 모양 성질을 만족한다는 의미) ○ 모양조건 (리스트를 이진트리로 해석) ▷ 마지막 레벨을 제외한 각 레벨의 노드는 모두 채워져 있어야 한다. ▷ 마지막 레벨에선 노드들이 왼쪽부터 채워져야 한다. ○ 값(key) 조건 ▷ 루트 노드를 제외한 모 든 노드에 저 장된 값(key)은 자신의 부모 노드의 값보다 크면 안된다. ★ 따라서 루트 노드에는 가장 큰 값이 저장되게 된다! ○ O(1)시간에 자식, 부모노드에 접근 가능 ▷A[k]의 왼쪽 자식노드 : A[2*k+1], 오른쪽 자식노드.. 2021. 7. 25. 이전 1 다음
