알고리즘 20 : Binary Heap(Max)

BinaryHeap

배열의 최대값, 최솟값을 찾아내는 메소드는 다음과 같다.

 

Math.max(...arr)
Math.min(...arr)

 

위 메소드들은 배열의 모든 요소를 순회한다. 이는 배열의 길이가 길때 연산시간이 오래걸린다는 단점이 있다.

 

 

BinaryHeap은 시간복잡도를 줄이면서 최대값, 최솟값을 빠르게 찾아내기 위한 자료구조 알고리즘이다.

 

 

이진 힙에서 부모 노드의 값이 자식 노드의 값보다 큰 경우를 최대 힙(max heap), 반대의 경우를 최소 힙(min heap)이라고 한다.

(이진 트리이므로 자식노드는 2개이다.)

---

문제

정수를 요소로 갖는 배열을 입력받아 이진 힙(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 타입을 요소로 갖는 배열을 리턴해야 합니다.

입출력 예시

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) {
  // TODO: 여기에 코드를 작성합니다.
  heap.push(item)
  //가장 마지막 요소, 지금 막 들어간 요소
  let lastIdx = heap.length-1
  //부모요소
  let parentIdx = getParentIdx(lastIdx)
  //만약 부모요소보다 가장 마지막요소(자식요소)가 크면 자리를 바꿀것.
  while(parentIdx>=0 && heap[parentIdx]<heap[lastIdx]){
    swap(parentIdx,lastIdx,heap)
    //그 다음 단계도 본다.
    //마지막 인덱스를 방금의 부모인덱스로 바꾼다.
    lastIdx = parentIdx
    //방금 바뀐 lastIdx의 부모인덱스를 구한다.
    parentIdx = getParentIdx(lastIdx)
    //만약 변경된 parentIdx보다 lastIdx가 크다면 또 다시 반복문으로 들어오고 아니라면 탈출한다.
  }
  return heap
}

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