힙 정렬
힙 정렬(heap sort)
수열을 정렬하는 알고리즘 중 하나. 힙이라는 자료구조를 사용하는것이 특징.
시간 복잡도: O(nlogn)
처음에는 힙에 모든 숫자를 저장한다. 힙은 내림차순으로 구축한다.
[ 5, 2, 7, 3, 6, 1, 4 ]
힙에 내림차순으로 구축하면 다음과 같은 모양이 된다.
힙에 저장된 숫자를 하나씩 꺼낸다.
내림차순 힙은 큰것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완료됩니다.
장단점
- 장점
- 시간 복잡도가 좋은 편(항상 nlogn을 보장)
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
- 단점
- 일반적으로 속도만 비교하자면 퀵정렬이 평균적으로 더 빠르다. 그래서 잘 사용하지 않는다.
힙 정렬(heap sort) js 코드
const buildHeap = (arr) => {
// build heap: 임의의 숫자들을 최대 힙으로 구성하는 연산과정
// 중간 값의 index 구하기
let i = Math.floor(arr.length / 2 - 1);
// 전달된 모든 배열 요소에서 최대 힙 구축
while (i >= 0) {
heapify(arr, i, arr.length);
i -= 1;
}
};
const heapify = (heap, i, max) => {
// heapify: 주어진 자료구조에서 힙 성질을 만족하도록 하는 연산
let index;
let leftChild;
let rightChild;
while (i < max) {
index = i;
// left child index 가져오기
leftChild = 2 * i + 1;
// right child index 가져오기
rightChild = leftChild + 1;
// left child가 last element가 아니거나, 값이 더 클 경우
if (leftChild < max && heap[leftChild] > heap[index]) {
index = leftChild;
}
// right child가 last element가 아니거나, 값이 더 클경우
if (rightChild < max && heap[rightChild] > heap[index]) {
index = rightChild;
}
// 위 조건 중 어느것도 해당하지 않을 경우 return
if (index === i) {
return;
}
// else swap
swap(heap, i, index);
// 스왑된 인덱스를 사용
i = index;
}
};
const swap = (arr, firstItemIndex, lastItemIndex) => {
const temp = arr[firstItemIndex];
// 배열의 첫번째 항목과 마지막 항목을 바꾼다.
arr[firstItemIndex] = arr[lastItemIndex];
arr[lastItemIndex] = temp;
};
const heapSort = (arr) => {
// 최대 힙을 구성
buildHeap(arr);
// last element의 index를 가져옴
lastElement = arr.length - 1;
while (lastElement > 0) {
swap(arr, 0, lastElement);
heapify(arr, 0, lastElement);
lastElement -= 1;
}
return arr;
};