힙정렬 (1) 썸네일형 리스트형 힙 정렬 Heap - 큰 키에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조. - 한 노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리를 기본으로 함. Heap 이 되기 위한 조건 1. 구조 조건 - 완전 이진 트리 2. 순서 조건 - Partial Order, 값의 순서가 직계 관계(부모-자식)에서만 성립. 이진 탐색 트리와의 비교 - 힙은 각 자식 < 부모. (최대 힙 트리라 가정.) - 이진 탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식. 따라서, 힙은 우선순위 정렬에, 이진 탐색 트리는 탐색에 강점을 지닌 자료구조. def heapify(unsorted, index, heap_size) : larg.. 이전 1 다음