힙 정렬
-
힙 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 18. 11:25
힙 정렬 루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다. 힙 만들기 입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다. 힙 생성 알고리즘 BuildHeap(A[], n) { for i ← └n / 2┘ downto 1 { Heapify(A, i, n); } } Heapfipy(A[], k, n) { left ← 2k; right ← 2k + 1; // 작은 자식 고르기 if (right ≤ n) then { if (A[left] < A[right]) then { smaller ← left; } else { smaller ← right; } } // 왼쪽 자식만 있는 경우 else if (left ≤ n) then { smaller ← left; } //..