JavaScript Algorithm - binaryHeap(maxHeap)

 

 

최대 힙(Max 힙이란 무엇일까요?)

 

최대 힙은 최대 트리면서 완전 이진 트리입니다. 

최대 트리 : 각 노드의 키값이 자식노드가 있다면 자식의 키값보다 크거나 같은 트리 

완전 이진 트리 : 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리, 자식노드가 반드시 2개 이하인 트리 

 

 

참고: 

https://juhee-maeng.tistory.com/94

[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)

 

문제

정수를 요소로 갖는 배열을 입력받아 이진 힙(binary heap)*을 리턴해야 합니다.

• 이진 힙(binary heap)은 노드의 값이 특정한 순서를 가지고 있는 완전 이진 트리(Complete Binary Tree)입니다.
• 완전 이진 트리는 이진 트리의 (마지막 레벨 또는 마지막 깊이를 제외하고) 모든 레벨이 노드로 가득 채워져 있어야 합니다. 마지막 레벨은 왼쪽부터 차례대로 채워져 있습니다.
• 이진 힙에서 부모 노드의 값이 (이진 트리이므로 2개의) 자식 노드의 값보다 큰 경우를 최대 힙(max heap), 반대의 경우를 최소 힙(min heap)이라고 합니다.

입력

인자 1 : arr

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

출력

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

주의사항

• 최대 힙(max heap)을 구현해야 합니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
• 최대 힙 구현을 위해 선언된 함수들(getParentIdx, insert)을 전부 완성해야 합니다.
• swap, getParentIdx, insert를 전부 사용해야 합니다.
• swap, binaryHeap을 수정하지 않아야 합니다.
• 테스트 케이스에서 힙 함수들을 정확히 구현했는지 함께 테스트합니다.
• insert의 시간 복잡도는 O(logN)입니다.
• 주어진 배열을 내림차순으로 정렬(O(logN))해도 최대 힙의 조건을 만족합니다. 하지만 이는 insert를 구현하는 것과는 거리가 먼 방법이며, 테스트를 통과할 수도 없습니다.

입출력 예시

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

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

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

 

풀이 코드

// 아래 코드는 수정하지 마세요.
function swap(idx1, idx2, arr) {
    // 두 변수를 바꾸는 방법
  
    // 1) 임시 변수를 활용한 방법
    // let temp = arr[idx1];
    // arr[idx1] = arr[idx2];
    // arr[idx2] = temp;
  
    // 2) Destructuring assignment를 활용한 방법
    // arr이 reference type이라 가능
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  
    // 3) XOR 연산을 활용한 방법
    // arr이 reference type이라 가능
    // arr[idx1] ^= arr[idx2];
    // arr[idx2] ^= arr[idx1];
    // arr[idx1] ^= arr[idx2];
  }
  
  //부모 인덱스를 구하는 함수 
  function getParentIdx(idx) {
    return Math.floor((idx - 1) / 2); 
  }
  
  //삽입함수 
  function insert(heap, item) {
    heap.push(item);
    let curIdx = heap.length - 1 ;
    console.log("curIdx",curIdx)

    let pIdx = getParentIdx(curIdx)
    console.log("pIdx",pIdx)
    
    //curIdx가 pIdx보다 크면 무한 반복 
    while(heap[curIdx] > heap[pIdx])
    {
        //curIdx, pIdx 위치 swap 
        swap(curIdx, pIdx, heap)
        //curIdx 값에 pIdx값 대입 
        curIdx = pIdx;
        //pIdx에 부모인덱스 값 대입 
        pIdx = getParentIdx(curIdx);
    }
    
    //힙 반환 
    return heap;
  }
  
  // reduce를 이용해서 배열을 새로 반환하고 이 때 insert 함수를 사용해서 배열을 반환함 
  const binaryHeap = function (arr) {
    return arr.reduce((heap, item) => {
      return insert(heap, item);
    }, []);
  };

 

조금 더 코드를 줄인다고 하면 다음과 같다.
풀이 코드2

function swap(idx1, idx2, arr) {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  
  // Get parent index function
  function getParentIdx(idx) {
    return Math.floor((idx - 1) / 2);
  }
  
  // Insert function
  function insert(heap, item) {
    heap.push(item);
    let curIdx = heap.length - 1;
    let pIdx = getParentIdx(curIdx);
    
    // Swap the values as long as `curIdx` is greater than `pIdx`
    while (heap[curIdx] > heap[pIdx]) {
      swap(curIdx, pIdx, heap);
      curIdx = pIdx;
      pIdx = getParentIdx(curIdx);
    }
    
    return heap;
  }
  
  // Binary heap function
  const binaryHeap = (arr) => arr.reduce(insert, []);

 

 

 

class로 구현된 maxHeap

 

class MaxHeap {
    constructor() {
      this.heap = [];
    }
  
    insert(value) {
      this.heap.push(value);
      this.heapifyUp();
    }
  
    extractMax() {
      if (this.heap.length === 1) return this.heap.pop();
      const max = this.heap[0];
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
      return max;
    }
  
    heapifyUp() {
      let currentIndex = this.heap.length - 1;
      while (currentIndex > 0) {
        const parentIndex = Math.floor((currentIndex - 1) / 2);
        if (this.heap[currentIndex] <= this.heap[parentIndex]) break;
        [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
        currentIndex = parentIndex;
      }
    }
  
    heapifyDown() {
      let currentIndex = 0;
      const lastIndex = this.heap.length - 1;
      while (currentIndex < lastIndex) {
        let childIndex = 2 * currentIndex + 1;
        if (childIndex < lastIndex && this.heap[childIndex] < this.heap[childIndex + 1]) {
          childIndex++;
        }
        if (this.heap[currentIndex] >= this.heap[childIndex]) break;
        [this.heap[currentIndex], this.heap[childIndex]] = [this.heap[childIndex], this.heap[currentIndex]];
        currentIndex = childIndex;
      }
    }
}

const heap = new MaxHeap();
const input = [4, 10, 3, 5, 1];
input.forEach(val => heap.insert(val));

console.log(heap.heap); // [10, 5, 3, 4, 1]
console.log(heap.extractMax()); // 10
console.log(heap.heap); // [5, 4, 3, 1]