heapSort(minHeap) 구현 Javascript

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

주의사항

• 힙 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
• 최소 힙(min heap)을 구현해야 합니다.
• 최소 힙 구현을 위해 선언된 함수들(getParentIdx, insert, removeRoot)을 전부 완성해야 합니다.
• swap, getParentIdx, insert, removeRoot를 전부 사용해야 합니다.
• swap, binaryHeap을 수정하지 않아야 합니다.
• 테스트 케이스에서 힙 함수들을 정확히 구현했는지 함께 테스트합니다.
  removeRoot의 시간 복잡도는 O(logN)입니다.

코드

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);
    let cIdx = heap.length - 1;
    let pIdx = getParentIdx(cIdx);
    
    while(pIdx >= 0 && heap[cIdx] < heap[pIdx]){
    	swap(cIdx, pIdx, heap);
        cIdx = pIdx;
        pIdx = getParentIdx(cIdx);
    }
    return heap;
}

function removeRoot(heap) {
	swap(0, heap.length - 1, heap);
    heap.pop();
    if(heap.length === 0) return [];
    
    let cIdx;
    let minIdx = 0;
    while(cIdx !== minIdx){
    	cIdx = minIdx;
        let left = cIdx * 2 + 1;
        let right = cIdx * 2 + 2;
        if(left < heap.length && heap[left] < heap[minIdx]){
			minIdx = left;        
        }
        
        if(right < heap.length && heap[right] < heap[minIdx]){
        	minIdx = right;
        }
        swap(cIdx, 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);
  let result = [];
  
  while(minHeap.length > 0){
  	result.push(minHeap[0]);
    minHeap = removeRoot(minHeap);
  }
  return result;
};

코드 풀이

최대힙과 달리 최대 힙을 (rootNode)를 삭제하면서 구현한다. 따라서 최대 힙 구현과 달리 removeRoot 함수를 구현하고, 함수 내부에서 좌, 우 나누어 트리를 만들어 나간다.
(실력이 부족해 자세한 설명이 힘들기 때문에 https://m.blog.naver.com/ndb796/221228342808 참고하는 걸로..)