Heap sort1 [Algorithm] 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ■ 정의 - 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조 - 힙(heap)을 사용하여 정렬하는 알고리즘 · 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리 · 최대힙: 부모노드 값(key 값) ≤ 자식노드 값 (key 값) · 최소힙: 부모노드 값(key 값) ≥ 자식노드 값 (key 값) ■ 인덱스 관계 - 부모노드 인덱스: a[(i-1) / 2] - 왼쪽 자식노드 인덱스: a[i * 2 + 1] - 오른쪽 자식노드 인덱스: a[i * 2 + 2] ■ 힙 정렬 과정 Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거 Step 2. 다시 힙을 .. 2023. 4. 8. 이전 1 다음