이진 힙

이진 힙

문제

정수를 요소로 갖는 배열을 입력받아 이진 힙(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;
  let pIdx = getParentIdx(curIdx);
  while (pIdx >= 0 && heap[curIdx] > heap[pIdx]) {
    swap(curIdx, pIdx, heap);
    curIdx = pIdx;
    pIdx = getParentIdx(curIdx);
  }
  return heap;
}

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

• 이진 힙은 트리 객체를 이용해 구현할 수도 있고, 배열로도 구현할 수 있습니다. 사실 거의 모든 트리를 배열로 구현할 수 있습니다. 트리를 배열로 구현했을 때의 장점은 (데이터가 선형적으로 저장되기 때문에) 저장공간을 절약할 수 있고 노드 접근 시 오버헤드(재귀호출, 반복문 등)가 약간 줄어듭니다. 다만 이를 위해서 매우 복잡한 인덱스 관리가 필요합니다. 반면, 트리 객체를 이용한 구현은 직관적(이해하기 쉬움)입니다. 그 대신 저장 공간과 약간의 오버헤드를 희생해야 합니다. 거의 모든 기술(구현)은 다수의 선택 사이의 트레이드 오프(trade-off)입니다. 무엇을 선택할 지는 요구사항(requirements), 즉 주어진 문제의 제약과 조건을 고려하여 결정해야 한다는 점이 가장 중요합니다.
• 완전 이진 트리는 노드가 낮은 레벨부터 채워지고, 같은 레벨에서는 왼쪽부터 채워지기 때문에 배열로 구현하는 것이 쉽습니다.
• 최대 힙과 이진 검색 트리(binary search tree)는 둘다 완전 이진 트리입니다. 하지만 이진 검색 트리에서는 모든 노드가 정렬되는 것과 달리 최대 힙에서는 오직 부모 노드와 직계 자식들 간의 관계만 유지됩니다. 이는 아래의 사실로부터 바로 알 수 있습니다.
  • 이진 검색 트리에서 오른쪽 자식 노드의 값은 부모 노드의 값보다 크지만, 최대 힙에서는 부모 노드의 값이 두 자식 노드의 값보다 크다.
• 아래와 같은 최대 힙에서 10을 삽입할 경우, 최대 힙을 유지하려면?

    9
   / \
  6   7
 / \ / \
4  5 2        <- 10

• 최소 힙은 부모 노드의 값이 두 자식 노드의 값보다 작다는 점을 제외하고는 최대 힙과 구현이 일치합니다.
  • 시각화 참고 링크 (https://www.cs.usfca.edu/~galles/visualization/Heap.html)

맨 위로