JavaScript Algorithm - binaryHeap(minHeap)

 

사전 지식

 

 

위키백과에서 본 힙 자료:

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)#:~:text=%ED%9E%99%EC%97%90%EB%8A%94%20%EB%91%90%EA%B0%80%EC%A7%80%20%EC%A2%85%EB%A5%98%EA%B0%80,%EB%8C%80%EC%86%8C%EA%B4%80%EA%B3%84%EA%B0%80%20%EC%A0%95%ED%95%B4%EC%A7%80%EC%A7%80%20%EC%95%8A%EB%8A%94%EB%8B%A4. 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

최대/최소 힙 정렬 참고로 봤던 자료: 

https://nyang-in.tistory.com/153

[자바스크립트 자료구조] 힙(Heap) - (1) 최소힙, 최대힙 구현

 

최소 힙과 힙 참고시 공부한 코드(위 블로그에 내용 있음) 

감을 익히기 위해 코딩하면서 참고했다.

 

힙 코드

 class heap {
    constructor(){
        this.items = [];
    }

    //값을 서로 바꾸는 메소드
    swap(index1, index2){
        let temp = this.items[index1];
        //items의 index1의 값을 temp(임시공간)에 담음
        this.items[index1] = this.items[index2]
        //index1에 index2 값 저장 
        this.items[index2] = temp;
        //index2에 temp값 저장  
    }

    //부모 인덱스 구하는 메소드
    parentIndex(index){
        return Math.floor((index - 1) / 2);
    }

    //왼쪽 자식 인덱스 구하는 메소드
    leftChildIndex(index){
        return index * 2 + 1;
    }

    //오른쪽 자식 인덱스 구하는 메소드
    rightChildIndex(index){
        return index * 2 + 2;
    }

    //부모 노드 구하는 메소드
    parent(index){
        return this.items[this.parentIndex(index)];
    }

    //왼쪽 자식 노드 구하는 메소드 
    leftChild(index){
        return this.items[this.leftChildIndex(index)];
    }

    //오른쪽 자식 노드 구하는 메소드
    rightChild(index){
        return this.items[this.rightChildIndex(index)];
    }

    //최대 힙의 경우 최댓값을 반환하고 최소힙의 경우 최솟값을 반환하는 메소드
    peek(){
        return this.items[0];
    }

    //힙의 크기(항목 개수)를 반환하는 메소드 
    size(){
        return this.items.length;
    }


 }

힙 코드를 상속한 최소 힙 코드

import "./heap"


class minHeap extends heap{
    //minHeap은 Heap 클래스를 상속받음 

    bubbleUp(){
        let index = this.items.length - 1;
        while(this.parent(index) !==undefined && this.parent(index) > this.items[index]){
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    bubbleDown(){
        let index = 0; 

        while(this.leftChild(index) !==undefined && (this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index])){

            let smallerIndex = this.leftChildIndex(index);
            if(this.rightChild(index) !==undefined && this.rightChild(index) <this.items[smallerIndex] ){
                smallerIndex = this.rightChildIndex(index);
            }

            this.swap(index, smallerIndex);

            index = smallerIndex;

        }
    }

    //힙에 원소를 추가하는 함수 
    add(item){
        this.items[this.items.length] = item; 
        this.bubbleUp();
    }

    //힙에서 원소를 빼내는 함수
    //최소 힙이라면 최솟값이 빠져나올 것이고 최대힙이면 최댓값이 빠져나옴
    poll(){
        let item = thsi.items[0] //첫 원소 keep
        this.items[0] = this.items[this.items.length - 1]; //맨 마지막 원소를 첫번째 원소로 복사
        this.items.pop(); //맨 마지막 원소 삭제
        this.bubbleDown();

        return item; //keep 해둔 값 반환.
    }
}

 

 

문제 설명: 정수를 요소로 갖는 중첩되지 않은 1차원 배열을 입력받는다. 이후  arr.sort를 사용하지 않고 힙정렬을 구현해야한다.

최소 힙 정렬을 구현해야하며 문제를 풀기 전 이진 힙정렬과 최대/최소 힙정렬을 공부할 것을 추천한다. 

 

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 -100,000 이상 100,000 이하의 정수
• arr.length는 100,000 이하

출력 

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.

주의사항

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

입출력 예시

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

output = heapSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

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

 

 

풀이 코드 

 

각 함수의 역할

• function swap(idx1, idx2, arr) : arr 배열에서 idx1과 idx2의 위치를 교환해주는 함수 
• function getParentIdx(idx) : 부모노드의 인덱스를 구하는 함수
  function insert(heap, item) : heap 배열에 item을 삽입하지만 부모노드가 현재 인덱스보다 값이 크면 인덱스 위치를 교환하고 heap을 리턴하는 함수
• function removeRoot(heap) : heap 배열을 입력받은 뒤 첫 번째 원소와 마지막 원소의 위치를 바꾸고 마지막 원소를 제거한 뒤 
• 여기서도 큰 값은 뒤로 보내고 작은 값은 앞으로 보내는 로직으로 동작한 뒤 heap을 반환한다. 
• function binaryHeap() : 이진힙 정렬 함수로 heap에 item을 삽입하는 insert를 수행하며 reduce를 통해 새로운 배열을 반환한다.
• const heapSort = function(arr) : heapSort 함수로 이진 힙정렬 함수 호출과 removeRoot 함수를 통해 최종 결과값인 sorted를 만들고 반환하는 메인함수다. 

 

//arr 배열에서 idx1, idx2의 위치를 교환하는 함수 
function swap(idx1, idx2, arr) {

  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

//부모노드의 인덱스를 구하는 함수 
function getParentIdx(idx) {
  // TODO: 여기에 코드를 작성합니다.
  return Math.floor((idx - 1) / 2);
}

//heap에 item을 insert함
//삽입하는 함수 
//heap 배열의 크기가 1 초과일때 조건문 작동
//부모인덱스 0 이상이고 부모인덱스가 현재 인덱스보다 클 경우 무한 루프
//curIdx(현재 인덱스)와 pIdx의 위치를 교환한 뒤 heap을 반환.
function insert(heap, item) {
  console.log("before heap",heap )
  // TODO: 여기에 코드를 작성합니다.
  heap.push(item);
  if (heap.length > 1) {
    let curIdx = heap.length - 1;
    let pIdx = getParentIdx(curIdx);
    console.log("curIdx", curIdx,"pIdx", pIdx)
    //curIdx가 pIdx 미만일 때 무한루프
    console.log("before while heap",heap)
    while (pIdx >= 0 && heap[curIdx] < heap[pIdx]) {
      //heap 배열에서 curIdx와 pIdx 위치 교환 
      swap(curIdx, pIdx, heap);
      //curIdx에 pIdx 값 대입 
      curIdx = pIdx;
      //pIdx는 curIdx의 부모인덱스 값 대입 
      pIdx = getParentIdx(curIdx);
    }
  }
  console.log("after heap",heap )
  return heap;
}

function removeRoot(heap) {
  //heap 배열에서 인덱스 0과 마지막을 교환 
  swap(0, heap.length - 1, heap);
  //heap 마지막 원소 제거 
  heap.pop();
  //힙 배열의 크기가 0 이면 빈 배열로 리턴 
  if (heap.length === 0) return [];

  //curIdx, minIdx 각각 값 선언 
  let curIdx;
  let minIdx = 0;
  //curIdx와 minIdx가 같지 않을 때 무한 루프
  while (curIdx !== minIdx) {

    curIdx = minIdx;
    //left는 curIdx * 2 + 1을 하는 이유는 right보다 작기 때문 
    let left = curIdx * 2 + 1;
    //right는 curIdx * 2 + 2를 하는 이유는 left 보다 커야함 
    let right = curIdx * 2 + 2;

    // minHeap before [ 1, 2, 4, 5, 3 ]
    // minHeap after [ 2, 3, 4, 5 ]
    
    //left가 heap 배열의 크기 미만이면서 heap[left]가 heap[minIdx]보다 미만일 경우
    if (left < heap.length && heap[left] < heap[minIdx]) {
      minIdx = left;
    }

    //right가 heap 배열의 크기 미만이면서 heap[right]가 heap[minIdx]보다 미만일 경우
    if (right < heap.length && heap[right] < heap[minIdx]) {
      minIdx = right;
    }

    //swap을 통해 더 작은 값이 뒤에있으면 앞의 값과 위치 교환함
    //curIdx와 minIdx 위치 교환 heap 배열에서 
    swap(curIdx, minIdx, heap);
  }

  return heap;
}

// 아래 코드는 수정하지 마세요.
const binaryHeap = function (arr) {
  //reduce로 새로운 배열을 반환
  return arr.reduce((heap, item) => {
    //insert 함수 호출 
    return insert(heap, item);
  }, []);
};

const heapSort = function (arr) {
  //minHeap에 binaryHeap 함수에 arr을 인자로 넣은 값을 저장 
  let minHeap = binaryHeap(arr);
  console.log("minHeap before",minHeap)
  //정답으로 반환할 sorted 배열 변수 선언 
  const sorted = [];
  //minHeap의 배열 크기가 0을 초과하는 동안 계속 루프 
  while (minHeap.length > 0) {
    //sorted에는 minHeap[0]을 삽입
    //최소값을 먼저 계속 넣으면서 정렬 
    sorted.push(minHeap[0]);
    //minHeap 변수에 removeRoot(minHeap)값을 저장 
    //removeRoot는 처음 원소와 마지막 원소 위치를 바꿈 
    console.log("sorted",sorted)
    console.log("minHeap before", minHeap)
    minHeap = removeRoot(minHeap);
    console.log("minHeap after", minHeap)
  }

  return sorted;
};



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

// output = heapSort([3, 1, 21]);
// console.log("output",output); // --> [1, 3, 21]

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

 

나는 코딩을 하면서 이해가 안되는 부분이 많아서 console.log로 찍어봤다.

다음은 console.log 결과값이다.

 

node 30_heapSort.js 
before heap []
after heap [ 5 ]
before heap [ 5 ]
curIdx 1 pIdx 0
before while heap [ 5, 4 ]
after heap [ 4, 5 ]
before heap [ 4, 5 ]
curIdx 2 pIdx 0
before while heap [ 4, 5, 3 ]
after heap [ 3, 5, 4 ]
before heap [ 3, 5, 4 ]
curIdx 3 pIdx 1
before while heap [ 3, 5, 4, 2 ]
after heap [ 2, 3, 4, 5 ]
before heap [ 2, 3, 4, 5 ]
curIdx 4 pIdx 1
before while heap [ 2, 3, 4, 5, 1 ]
after heap [ 1, 2, 4, 5, 3 ]
minHeap before [ 1, 2, 4, 5, 3 ]
sorted [ 1 ]
minHeap before [ 1, 2, 4, 5, 3 ]
minHeap after [ 2, 3, 4, 5 ]
sorted [ 1, 2 ]
minHeap before [ 2, 3, 4, 5 ]
minHeap after [ 3, 5, 4 ]
sorted [ 1, 2, 3 ]
minHeap before [ 3, 5, 4 ]
minHeap after [ 4, 5 ]
sorted [ 1, 2, 3, 4 ]
minHeap before [ 4, 5 ]
minHeap after [ 5 ]
sorted [ 1, 2, 3, 4, 5 ]
minHeap before [ 5 ]
minHeap after []
output [ 1, 2, 3, 4, 5 ]