binary heap

binary heap

binary heap(이진힙)은 노드의 값이 특정한 순서를 가지고 있는 complete binary tree(완전이진트리)다. 이진힙은 부모노드가 자식노드보다 항상 큰 max heap(최대힙)과 부모노드가 자식노드보다 항상 작은 min heap(최소힙)이 있다. 따라서 노드의 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 자료구조이다

완전이진트리(complete binary tree)는 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져있고, 마지막 레벨의 모든 노드는 가능한 가장 왼쪽에 있다.

binary heap과 객체, 배열

이진 힙은 트리 객체를 이용해 구현할 수도 있고, 배열로도 구현할 수 있다. 사실 거의 모든 트리를 배열로 구현할 수 있다.
트리를 배열로 구현했을때의 장점은(데이터가 선형적으로 저장되기 때문에) 저장공간을 절약할 수 있고, 노드 접근 시 오버헤드(재귀, 반복문)가 약간 줄어든다. 다만, 이를 위해서 매우 복잡한 인덱스 관리가 필요하다.
반면, 트리 객체를 이용한 구현은 직관적(이해하기 쉬움)이다. 그 대신 저장 공간과 약간의 오버헤드를 희생해야 한다. 거의 모든 기술은 다수의 선택 사이의 트레이드 오프(trade-off)이다. 무엇을 선택할지는 요구사항, 즉 문제의 제약과 조건을 고려하여 결정해야 한다.

binary heap과 binary search tree 비교

이진힙에서는 오직 부모와 직계자식 노드간에의 관계만 유지되지만 이진탐색트리에서는 모든 노드가 정렬된다.

문제

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

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

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

주의사항

• 최대힙을 구현해야합니다
• insert의 시간 복잡도는 O(logN)입니다.

//2개의 인덱스와 배열이 주어졌을때, 두개의 인덱스 값을 맞바꾸는 함수
function swap(idx1, idx2, arr){
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

//부모노드의 인덱스를 구하는 함수
function getParentIdx(idx){
  return Math.floor((idx-1)/2);
}

//부모노드의 인덱스가 0보다 크거나 같고, 자식노드 > 부모노드일때 swap을 반복하는 함수
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);
  },[]);
}