힙 정렬

Vorhandenheit ·2021년 11월 11일

알고리즘과 자료구조

목록 보기

5/16

힙 정렬

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는 정렬 알고리즘입니다.

힙이란?

최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

완전 이진 트리

이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드를 말합니다. 완전 이진 트리는 루트 노드부터 시작해서 자식 노드가 왼쪽, 오른쪽 차근차근 들어가는 구조의 이진트리를 말합니다.

힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘입니다.

코드

let arrLen;

function swap(input, i, j) { // 주어진 배열의 수를 바꾸는 함수
  let temp = input[i];
  input[i] = input[j];
  input[j] = temp;
}

function heapRoot(input, i) {
  let left = 2 * i + 1; 
  let right = 2 * i + 2;
  let max = i;
// 힙 생성 알고리즘, 3수를 골라서 서로 비교해서, max에 들어갈 수를 고른다
  if (left < arrLen && input[left] > input[max]) { 
    max = left;
  }
	//2를 곱해서 전체길이보다 left가 길수도 있는 걸 방지, 서로 값을 비교한다
  if (right < arrLen && input[right] > input[max]) {
    max = right;
  }
	
	//2를 곱해서 전체길이보다 right가 길수도 있는 걸 방지, 서로 값을 비교한다
  if (max != i) { // 비교하고나서 값이 바뀌었다면 
    swap(input, i, max); // 자리를 바꾸고
    heapRoot(input, max); //다시 돌린다.
  }
}

function heapSort(input) {
  arrLen = input.length;

  for (let i = Math.floor(arrLen / 2); i >= 0; i--) { //완전 이진 트리
    heapRoot(input, i);
  }

  for (let i = input.length - 1; i > 0; i--) {
    swap(input, 0, i); // 오름차순으로 바꿈
    arrLen--;

    heapRoot(input, 0); // 바꾸면서 확인
  }
}

let nums = [1, 3, 5, 6, 2, 0, 8, 9, 7, 4];

heapSort(nums); // 힙 정렬 시행
console.log(nums);
> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]