[Algorithm] 힙 정렬(Heap Sort) 구현하기 Node.js/Javascript

힙 정렬(Heap Sort)은 최대 힙 / 최소 힙을 구현한 후 정렬을 진행하는 방식입니다. 힙 정렬은 1964년 J.W.J 윌리엄스에 의해 발명됩니다. 힙 정렬의 시간복잡도는 먼저 최소 힙/최대 힙을 구현해야 O(log N)이 소요되고, 구성된 힙 트리에서 정렬을 구현하는데 N 번의 연산이 필요하므로 총 O(N log N)이 필요합니다.

 

 

힙 정렬 알고리즘

힙 정렬 알고리즘 순서는 다음과 같습니다.

1. 주어진 배열을 통해 최소 힙/ 최대 힙을 구현합니다.
2. 루트의 값과 자식 노드의 값을 비교하면서 값을 출력합니다.
3. 최소 힙/ 최대 힙의 길이가 0이 될 때 까지 위 과정을 반복합니다.

 

예를 들어 arr=[5, 4, 3, 2, 1]이 주어집니다. 최소 힙을 구하면 다음과 같습니다. 

최소 힙을 기반으로 정렬을 진행하면 루트 값인 1과 마지막 요소인 3을 swap한 후 1을 빼서 sorted 배열에 추가합니다. 이유는 최소 힙을 구성할 경우 루트 값은 해당 배열에서 가장 작은 값이 되기 때문입니다. 

루트 값인 3과 자식 노드 2 와 4를 비교해 루트 값보다 작은 값을 찾습니다. 이제 2가 가장 작은 값이자 루트값이 됩니다.

 

다시 루트값과 가장 마지막 값을 swap한 후 정렬된 2를 sorted 배열에 추가합니다. 이제 루트 값은 5가 되고 자식 노드 3과 4와의 비교를 이어나갑니다. 비교 순서는 left, right 순서로 진행되며 5의 정렬 후 위치는 4 오른쪽에 위치합니다.

루트 값 5는 3보다 큰 수이므로 swap이 진행됩니다.

정렬된 3은 sorted 배열에 추가되고, 4와 5만 minHeap 배열에 남게 됩니다. 루트 노드 4는 5보다 작으므로 추가적인 정렬 연산은 이뤄지지 않습니다. 이제 4를 출력해서 sorted 배열에 넣고, 5를 sorted 배열에 추가하면 minHeap 배열의 길이는 0이 되고, 정렬 연산은 종료됩니다. 

힙 정렬 출처 : 위키백과

 

 

문제

 

정수를 요소로 가지는 배열을 입력 받아 힙 정렬을 구현해 오름차순으로 정렬된 배열을 반환합니다.

 

입/출력

 

입력

• Number 타입 요소를 가지는 배열
• -100,000 <= arr[i] <= 100,000
• arr.length <= 100,000

출력

• Number 타입 요소를 가진 오름차순 정렬된 배열

 

 

주의사항

 

• 힙 정렬을 구현해야 합니다.
• arr.sort() 사용이 금지됩니다.
• 입력으로 주어진 배열은 중복없는 1차원 배열입니다.
• 최소 힙(Min Heap)을 구현합니다.

 

구현

 

오름차순 정렬을 하기 위해 먼저 최소 힙을 구현합니다. 최소 힙을 구현하기 위해서는 swap(), getParentIdx(), insert() 메소드를 사용합니다. 최대 힙을 구현하는 방법은 아래 글을 참고해주세요.

 

[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript

 

swap() 함수 구현

function swap(idx1, idx2, arr) {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }

 

getParentIdx() 함수 구현

 function getParentIdx(idx) {
    return Math.floor((idx-1)/2);
  }

 

insert() 함수 구현

  function insert(heap, item) {

    // 최소 힙을 만든다.
    heap.push(item);
  
    if(heap.length > 1){
        let currentIdx = heap.length - 1;
        let parentIdx = getParentIdx(currentIdx);
      
        while(parentIdx >= 0 && heap[currentIdx] < heap[parentIdx]){
          swap(currentIdx, parentIdx, heap);
          currentIdx = parentIdx;
          parentIdx = getParentIdx(currentIdx);
        }
    }
  
    return heap;
  }

 

최소 힙을 구현한 후 정렬을 진행하기 위해서는 루트 값을 제거하는 로직이 필요합니다. 제거된 루트 값은 정렬된 새로운 배열인 sorted 배열에 추가됩니다. 

 

removeRoot() 함수 구현

function removeRoot(heap) {
    
    swap(0, heap.length-1, heap);
    heap.pop();
    if(heap.length === 0) return [];

    let currentIdx;
    let minIdx = 0;
    while(currentIdx !== minIdx){
        currentIdx = minIdx;
        let left = currentIdx * 2 + 1;
        let right = currentIdx * 2 + 2;

        if(left < heap.length && heap[left] < heap[minIdx]){
            minIdx = left;
        }
        if(right < heap.length && heap[right] < heap[minIdx]){
            minIdx = right;
        }

        swap(currentIdx, minIdx, heap);
    }
    return heap;
  
  }

 

마지막으로 binaryHeap 구현 함수를 작성하고 heapSort() 함수를 구현합니다.

 const binaryHeap = function (arr) {
    return arr.reduce((heap, item) => {
      return insert(heap, item);
    }, []);
  };
  
  const heapSort = function (arr) {
    let minHeap = binaryHeap(arr);
    
    const sorted = [];

    while(minHeap.length > 0){ 
        sorted.push(minHeap[0]);
        minHeap = removeRoot(minHeap);
    }

    return sorted;

  };

 

 

 

힙 정렬 Node.js 소스

function swap(idx1, idx2, arr) {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  
  function getParentIdx(idx) {
    return Math.floor((idx-1)/2);
  }
  
  function insert(heap, item) {

    // 최소 힙을 만든다.
    heap.push(item);
  
    if(heap.length > 1){
        let currentIdx = heap.length - 1;
        let parentIdx = getParentIdx(currentIdx);
      
        while(parentIdx >= 0 && heap[currentIdx] < heap[parentIdx]){
          swap(currentIdx, parentIdx, heap);
          currentIdx = parentIdx;
          parentIdx = getParentIdx(currentIdx);
        }
    }
  
    return heap;
  }
  
  function removeRoot(heap) {
    
    swap(0, heap.length-1, heap);
    heap.pop();
    if(heap.length === 0) return [];

    let currentIdx;
    let minIdx = 0;
    while(currentIdx !== minIdx){
        currentIdx = minIdx;
        let left = currentIdx * 2 + 1;
        let right = currentIdx * 2 + 2;

        if(left < heap.length && heap[left] < heap[minIdx]){
            minIdx = left;
        }
        if(right < heap.length && heap[right] < heap[minIdx]){
            minIdx = right;
        }

        swap(currentIdx, minIdx, heap);
    }
    return heap;
  
  }
  
  const binaryHeap = function (arr) {
    return arr.reduce((heap, item) => {
      return insert(heap, item);
    }, []);
  };
  
  const heapSort = function (arr) {
    let minHeap = binaryHeap(arr);
    
    const sorted = [];

    while(minHeap.length > 0){ 
        sorted.push(minHeap[0]);
        minHeap = removeRoot(minHeap);
    }

    return sorted;

  };
  output = heapSort([4, 10, 3, 5, 1]);
console.log(output); // --> [1, 3, 4, 5, 10]

// let output = heapSort([5, 4, 3, 2, 1]);
// console.log(output); // --> [1, 2, 3, 4, 5]

 

 

 

 

[Blockchain] 클레이튼(Klaytn) 블록체인 이란?

 

[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript

 

[Algorithm] 기수 정렬 계수 정렬 Node.js

 

[Algorithm] 최단거리 알고리즘 문제 Node.js