Algorithm problem-29

1. 문제

• 정수를 요소로 갖는 배열을 Max heap으로 리턴하라

2. 시도

• 변수를 치환하는 함수는 구현되어 있음
• 부모의 idx를 찾는 함수와 heap에 item을 추가하는 함수를 구현할 것
• 부모 노드의 idx를 search하는 함수
• 완전이진트리의 구조이기에 가능
• 0 - 1 - 3 - 7-15,16/8-17,18
• 0 - 1 - 4 - 9-19,20/10-21,22
• 0 - 2 - 5 - 11-23,24/12-25,26
• 0 - 2 - 6 - 13-27,28/14-29,30
• 1과 2의 부모는 0
• 홀수이면 2로 나눈 수의 parseInt값?
• 짝수이면 2로 나눈 수 -1?
• 위 조건을 코드로 짜 보았다
• 위 조건을 코드 한 줄로 짜는게 가능했다...
• 다음으로 item을 heap에 추가하는 함수
• 초기값이 빈 배열인 것을 나중에 알았다
• 이미 포함되어 있는 값으로 착각하여 코드를 짜다보니 결국엔 실패
• heap에 item을 push하고 시작하니 잘 되었음, 레퍼런스와 거의 유사함
• runJS에서 잘 실행되었는데, 코플릿에서 실행 초과가 떠서 원인을 찾던 중
• item의 idx를 저장하는 부분을 indexOf로 돌려서였음, length - 1로 교체

3. 수도코드

// swap과 binearyHeap은 레퍼런스를 참조
function getParentIdx(idx) {
  // 1과 2의 부모는 0
  if (idx === 1 || idx === 2) return 0;
  // 짝수이면? 자신을 2로 나눈 수 -1 값
  if (idx % 2 === 0) return (idx / 2 - 1);
  // 홀수이면? 자신을 2로 나눈 수의 parseInt값
  else return (parseInt(idx / 2));
}

function insert(heap, item) {
  // heap에서 item의 idx를 저장
  let idx = heap.indexOf(item);
  // 부모노드의 idx를 변수에 저장
  let pIdx = getParentIdx(idx);
  while (heap[pIdx] < heap[idx]) {
    swap(idx, pIdx, heap);
    idx = pIdx;
    pIdx = getParentIdx(pIdx);
  }
  return heap;
}

4. 레퍼런스

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 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);
  }, []);
};