힙 정렬(heap sort)

힙 정렬은 최댓값, 최솟값을 찾는 데 특화된 정렬 방법이다. 해결해야 할 문제가 최대, 최솟값을 찾아내는 것이라면 힙 정렬을 사용해야 할 수도 있다.

 

힙(heap):

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이며 힙 속성을 만족한다.

 

완전 이진 트리(complete binary tree):

완전 이진트리는 각각의 노드가 최대 "두 개"의 자식 노드를 가지는 트리 자료구조이다. 가장 위에 존재하는 노드를 루트 노드(root node)라고 한다. 

이진트리에는 레벨이 존재한다. 루트 노드가 위치하는 가장 상단 레벨부터 Level 0 이다. 내려갈수록 레벨이 증가한다.

이진트리에도 종류가 많지만 아래의 조건을 충족해야만 완전 이진 트리로 분류될 수 있다.

• 마지막 레벨을 제외하고 모든 노드가 꽉 차있어야 한다.
• 노드는 왼쪽에서 오른 쪽으로 채워져야만 한다.

만약 왼쪽이 빈 상태로 오른쪽 자식 노드만 채워진 상태라면 완전 이진 트리가 될 수 없다.

 

힙 정렬의 순서

• 1단계: 정렬해야 할 n개의 원소를 사용해 최대힙(max heap) 형태의 완전 이진 트리를 만든다.
• 2단계: 한 번에 하나씩 원소를 힙에서 꺼낸 후 배열의 뒤부터 저장한다.
• 3단계: 2단계를 반복하면, 최댓값부터 값이 감소하는 순서로 배열에 저장된다.

 

힙에는 최대힙과 최소힙이 존재한다.

 

최대힙의 특징

• 각 노드의 값이 해당 노드의 자식 노드들의 값보다 크거나 같다.
• 루트 노드에는 전체 힙에서 가장 큰 값이 위치한다.
• 우선순위 큐에서는 가장 큰 값이 우선적으로 처리되어야 할 때 사용된다.

 

최소힙의 특징

• 각 노드의 값이 해당 노드의 자식 노드들의 값보다 작거나 같다.
• 루트 노드에는 전체 힙에서 가장 작은 값이 위치한다.
• 우선순위 큐에서는 가장 작은 값이 우선적으로 처리되어야 될 때 사용된다.

 

최대힙과 최소힙은 정렬과 방향의 차이가 존재한다. 그러므로 만약 힙 정렬을 할 때,  내림차순으로 정렬이 필요하다면 최대 힙, 오름차순으로 정렬이 필요하다면 최소 힙을 사용할 수 있다. 

 

 

힙 정렬의 시간 복잡도

힙 정렬은 시간복잡도가 좋다. 모든 경우에 O(n log n)의 시간 복잡도를 가진다. 또한 이진 트리 노드의 특성을 활용해 최댓값, 최솟값을 추출하는 데 유용하다.

 

힙 정렬의 공간복잡도

힙 정렬의 공간 복잡도는 2가지 패턴이 나타날 수 있다.

• In-place 힙 정렬: 추가적인 공간을 사용하지 않고 입력 배열 내에서 정렬을 수행하는 방식. 이 경우 힙 정렬의 공간 복잡도는 O(1)이다.
• Out-place 힙 정렬: 추가적인 입력 배열을 생성하여 정렬을 만들고 수행한다. 이 경우 추가 생성 배열의 크기는 입력 배열 크기에 비례한다.

 

힙 정렬은 불안정 정렬이다. 대부분 힙을 구성할 때 기존 배열의 순서와 무관하게 최대 힙을 구성하는 데 중점을 둔다. 이 과정에서 동일 값의 순서 변경이 발생할 여지가 있다. 또한 루트 노드 선택 과정에서 가장 큰 값 또는 작은 값을 택하게 되는데 동일한 값이 여러 개인 경우, 상대적인 순서가 유지되기 어렵다. 이러한 이유에서 안정 정렬이 필요한 경우라면 힙정렬은 좋은 선택지가 아닐 수 있다.

 

 

----------------------

 

 

 

1. 기본 개념
- 완전 이진트리 구조를 사용
- 부모-자식 간의 대소관계가 정해짐
  * 최대 힙: 부모 > 자식
  * 최소 힙: 부모 < 자식

2. 구현 시 알아야 할 공식

부모 노드 인덱스 = (자식 인덱스 - 1) // 2
왼쪽 자식 인덱스 = (부모 인덱스 * 2) + 1
오른쪽 자식 인덱스 = (부모 인덱스 * 2) + 2

3. 정렬 과정 (최대 힙 기준)
- 배열을 힙으로 변환(heapify)
- 루트(최댓값)를 배열 마지막과 교환
- 힙 크기 1 감소
- 다시 heapify
- 반복

4. 시간 복잡도
- 평균: O(n log n)
- 최악: O(n log n)
- 최선: O(n log n)

5. 공간 복잡도
- O(1) : 추가 메모리 거의 불필요

6. 특징
- 불안정 정렬 (같은 값의 순서 보장 X)
- 제자리 정렬 (추가 메모리 필요 X)
- 최악의 경우에도 O(n log n) 보장

7. 장단점
장점:
- 추가 메모리 필요 없음
- 최악의 경우에도 성능 보장

단점:
- 불안정 정렬
- 캐시 효율이 나쁨
- 같은 O(n log n) 알고리즘 중 실제로는 퀵소트보다 느림

8. 주 사용처
- 우선순위 큐 구현
- 메모리가 제한적일 때
- 최악의 경우에도 성능 보장 필요할 때

9. 기본형(최대힙)

function heapSort(arr) {
    const n = arr.length;
    
    // 1. 초기 힙 만들기
    for(let i = Math.floor(n/2 - 1); i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 2. 정렬하기
    for(let i = n-1; i > 0; i--) {
        // 최댓값(루트)를 맨 뒤로 보내기
        [arr[0], arr[i]] = [arr[i], arr[0]];
        // 힙 다시 만들기
        heapify(arr, i, 0);
    }
    
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    // 왼쪽 자식이 더 크면
    if(left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 오른쪽 자식이 더 크면
    if(right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 교환이 필요하면
    if(largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

 

히피파이(힙을 만드는 과정)에 대한 도표화

배열 [4, 10, 3, 5, 1]을 예시로 heapify 과정을 설명

초기상태
	4(0)
      /    \
   10(1)   3(2)
   /  \
5(3)  1(4)



1단계 (i=1일 때):
// left=3, right=4, largest=1 시작
       4(0)
      /    \
   10(1)   3(2)
   /  \
5(3)  1(4)

// 10과 자식들 비교 후 변화 없음


2단계 (i=0일 때):
// left=1, right=2, largest=0 시작
       4(0)
      /    \
   10(1)   3(2)
   /  \
5(3)  1(4)

// 4 < 10이므로 largest = 1
// swap 발생
       10(0)
      /    \
   4(1)    3(2)
   /  \
5(3)  1(4)

// 재귀: 4의 위치에서 다시 heapify
       10(0)
      /    \
   5(1)    3(2)
   /  \
4(3)  1(4)



//최종 최대힙
	10(0)
      /    \
   5(1)    3(2)
   /  \
4(3)  1(4)

 

주의할 것은 heapify 함수를 사용한다고 해서 배열이 정렬된다고 생각해서는 안된다는 것이다. 이 함수는 배열을 이진 트리 구조로 만들어 부모와 자식의 관계를 정리해 주는 것 뿐이다. 이를 배열의 구조로 봤을 때는 전혀 정렬된 것이 아니다.

 

예를 들어 최대힙으로 만든다고 하면, 루트 노드에는 가장 큰 값이 오게 되고, 그 아래부터 계속해서 부모 노드가 자식 노드보다 큰 값을 가지는 구조가 만들어지게 된다. 그러나 이를 배열의 구조에서 바라봤을 때 내림차순으로 정렬되어 있지는 않은 것이다. 따라서 heapSort함수에서 힙의 정렬을 수행하게 되는 것이다.

 

 

 

예제1)

/*
 100개의 보물을 찾은 모험가

보물 상자 겉면에 쓰여있는 숫자에 따라서 숫자가 클수록 더 귀한 보물이 담겨있다
100개의 보물 상자 중 가장 귀한 보물상자들만 챙기려면?
*/


let treasureBoxs = [2, 5, 20, 602, 49, 856, 10, 1, 5, 298, 457, 21, 790, 988
]

function heapify(arr, n, i) {
  // 배열과, 배열의 길이와, 인덱스를 전달받는다.
  // 루트 노드
  let largest = i;

  // 자식노드 구성. 이진트리라 양쪽이 있으므로 2를 곱해서 +1 해줘야 함. 1-0-2, 3-1-4, 5-2-6 
  let left = 2 * i + 1; // 왼쪽 자식
  let right = 2 * i + 2; // 오른쪽 자식

  // 왼쪽이 배열의 길이보다 작고, 배열의 왼쪽 인덱스 값이 현재 최댓값보다 크다면, 최댓값에 왼쪽 값을 할당
  if ( left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  // 오른쪽이 배열의 길이보다 작고, 배열의 오른쪽 인덱스 값이 현재 최댓값보다 크다면, 최댓값에 오른쪽 값을 할당
  if ( right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // 만약 최댓값이 파라미터로 넘어온 i값과 다르다면, 배열의 i번째 값과 최댓값을 바꾼다.
  if (largest != i) {
    let swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;
    // [arr[i], arr[largest]] = [arr[largest], arr[i]];]]

    // 함수를 재귀 호출하여 힙을 다시 구성한다.
    heapify(arr, n, largest);
  }
}

function heapSort(arr) {

  let n = arr.length;

  // 1. 배열의 길이를 반으로 나눠서 버림한 값에서 1을 뺀 값을 인덱스로 지정. i는 0이상이고 계속해서 감소.
  //(non-leaf) 노드부터 시작해서 최대 힙 구성. n/2-1부터 시작하는 이유: 리프 노드는 자식이 없어서 heapify가 필요 없음
  for (let i = Math.floor(n / 2) - 1; i>= 0; i-- ) {
    // 조건을 만족할 때까지 힙을 생성
    heapify(arr, n, i);
  }

  // 힙 정렬과정
  // 인덱스를 배열길이-1로 설정하고, 인덱스가 0보다 크며 인덱스가 순회 시마다 감소
  for (let i = n - 1; i > 0; i--) {
    let temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    //[arr[0], arr[i]] = [arr[i], arr[0]];]
    heapify(arr, i, 0);
  }
}

heapSort(treasureBoxs);
console.log(treasureBoxs)
console.log(treasureBoxs.reverse())


/*

[
  1,   2,   5,   5,  10,  20,
 21,  49, 298, 457, 602, 790,
856, 988
]
[
988, 856, 790, 602, 457, 298,
 49,  21,  20,  10,   5,   5,
  2,   1
]
*/


/*

자식 노드 찾기

왼쪽 자식 = 2 * i + 1
오른쪽 자식 = 2 * i + 2


부모 노드 찾기
부모 = Math.floor((i - 1) / 2)
  // 인덱스 3(값 2)의 부모 찾기
  Math.floor((3 - 1) / 2) = 1  // 값 5

  ------

if ( left < n && arr[left] > arr[largest]) {
  largest = left;
}

  left < n 조건이 필요한 이유
  n은 배열의 길이
  배열 범위를 벗어나지 않도록 체크
  자식 노드가 실제로 존재하는지 확인


  arr[left] > arr[largest] 조건이 필요한 이유

  최대 힙의 규칙: 부모는 자식보다 커야 함
  largest는 현재 검사 중인 부모 노드의 인덱스
  왼쪽 자식이 더 크면 교환이 필요

  오른쪽에 대한 조건문도 같은 이유이다.
  그러나 완전 이진트리의 특성상 왼쪽부터 채워져야 하므로 왼쪽을 검사하는 로직이 먼저 등장해야 한다.


*/

 

 

예제2.

/*
조금 까다로운 손님을 만난 바텐더
- 손님은 가장 도수가 높은 위스키와 가장 낮은 위스키 한잔씩을 원한다.
- 이 가게에는 위스키의 종류가 100종류가 되며 각각 다른 도수를 가지고 있다.
- 술이 너무 많았기 때문에 손님은 바텐더에게 30초만 살펴보고 그 중 최고도수와 최저도수 위스키를 요청했다.
- 바텐더는 두 술의 도수를 비교해 순서를 변경하는 데 매번 1초가 걸렸다.
*/

// 위스키 배열 생성 (1~100 사이 소수점 포함)
let whiskeys = Array.from({ length: 100 }, () => Math.random() * 100 + 1);
console.log("원본 위스키 배열:", whiskeys);

let timeLeft = 30;  // 제한시간
let comparisons = 0;  // 비교 횟수 추적

// 최대 힙 구성을 위한 heapify 함수
function maxHeapify(arr, n, i) {
    if (timeLeft <= 0) return;  // 시간 초과시 중단
    
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    if (left < n) {
        comparisons++;
        timeLeft--;
        if (arr[left] > arr[largest]) {
            largest = left;
        }
    }
    
    if (right < n && timeLeft > 0) {
        comparisons++;
        timeLeft--;
        if (arr[right] > arr[largest]) {
            largest = right;
        }
    }
    
    if (largest !== i && timeLeft > 0) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        maxHeapify(arr, n, largest);
    }
}

// 힙 정렬 함수
function findMaxWhiskey(arr) {
    const n = arr.length;
    
    // 최대 힙 구성
    for (let i = Math.floor(n / 2) - 1; i >= 0 && timeLeft > 0; i--) {
        maxHeapify(arr, n, i);
    }
    
    return arr[0];  // 루트가 최댓값
}

// 배열 복사해서 최댓값 찾기
let arrForMax = [...whiskeys];
const maxWhiskey = findMaxWhiskey(arrForMax);

// 남은 시간으로 최솟값 찾기 시도
// 최소 힙 구성을 위한 heapify 함수
function minHeapify(arr, n, i) {
    if (timeLeft <= 0) return;
    
    let smallest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    if (left < n) {
        comparisons++;
        timeLeft--;
        if (arr[left] < arr[smallest]) {
            smallest = left;
        }
    }
    
    if (right < n && timeLeft > 0) {
        comparisons++;
        timeLeft--;
        if (arr[right] < arr[smallest]) {
            smallest = right;
        }
    }
    
    if (smallest !== i && timeLeft > 0) {
        [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
        minHeapify(arr, n, smallest);
    }
}

function findMinWhiskey(arr) {
    const n = arr.length;
    
    // 최소 힙 구성
    for (let i = Math.floor(n / 2) - 1; i >= 0 && timeLeft > 0; i--) {
        minHeapify(arr, n, i);
    }
    
    return arr[0];  // 루트가 최솟값
}

let minWhiskey;
if (timeLeft > 0) {
    let arrForMin = [...whiskeys];
    minWhiskey = findMinWhiskey(arrForMin);
}

console.log("수행된 비교 횟수:", comparisons);
console.log("남은 시간:", timeLeft);
console.log("가장 높은 도수의 위스키:", maxWhiskey);
console.log("가장 낮은 도수의 위스키:", minWhiskey || "시간 부족으로 찾지 못함");

 

 

아래처럼 단순 비교가 나을 수 있다.

let whiskeys = Array.from({ length: 100 }, () => Math.random() * 100 + 1);
let availableTime = 30;
let comparisons = 0;

// 단순하게 한 번의 순회로 최대값과 최소값을 동시에 찾기
function findMinMax(arr) {
    let max = arr[0];
    let min = arr[0];
    
    for(let i = 1; i < arr.length && comparisons < availableTime; i++) {
        comparisons++; // max 비교
        if(arr[i] > max) {
            max = arr[i];
        }
        
        comparisons++; // min 비교
        if(arr[i] < min) {
            min = arr[i];
        }
    }
    
    return { max, min };
}

const result = findMinMax(whiskeys);

console.log(`비교 횟수: ${comparisons}`);
console.log(`도수가 가장 높은 위스키: ${result.max}`);
console.log(`도수가 가장 낮은 위스키: ${result.min}`);