힙(Heap)

최대값 또는 최솟값을 빠르게 찾기 위해 사용되는 알고리즘

• 완전 이진 트리의 형태를 가지며 최대힙과 최소힙으로 나뉨
  • 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 성질을 가짐 (루트 노드가 가장 큼)
  • 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 성질을 가짐 (루트 노드가 가장 작음)
• 주로 우선순위 큐를 구현하는데 밑받침되는 자료구조로 쓰임

이진트리와의 차이점

• 이진트리와는 다르게 층(level)으로 대소 관계를 구분
• 힙트리에서는 중복된 값을 허용(이진 탐색 트리에서는 중복된 값 허용 X)

⏱️ 시간복잡도

• 삽입: O(log N)
• 삭제: O(log N)
• 최댓값/최솟값 조회(peek): O(1)
• 힙 정렬: O(N log N)

⌨️ 구현하기

Heap에 대한 ADT

ADT	설명
insert(value)	새로운 요소를 힙에 추가하고, 힙 속성을 유지하도록 조정(Heapify Up)
remove	힙의 루트(최대/최소값)를 제거하고, 마지막 요소를 루트로 이동한 후 조정(Heapify Down)
peek	힙의 루트(최대/최소값) 요소를 확인(삭제하지 않음)
size	힙에 저장된 요소 개수를 반환
isEmpty	힙이 비어있는지 여부를 반환
heapify(array)	주어진 배열을 힙으로 변환
heapSort(array)	힙을 사용하여 배열을 정렬

최소 힙(Max Heap)

const createMinHeap = () => {
  const heap = [];

  const getLeftChildIndex = (parentIndex) => 2 * parentIndex + 1;
  const getRightChildIndex = (parentIndex) => 2 * parentIndex + 2;
  const getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  const swap = (index1, index2) => {
    [heap[index1], heap[index2]] = [heap[index2], heap[index1]];
  };

  const insert = (value) => {
    heap.push(value);
    heapifyUp();
  };

  const heapifyUp = () => {
    let index = heap.length - 1;
    while (index > 0) {
      const parentIndex = getParentIndex(index);
      if (heap[parentIndex] <= heap[index]) break;
      swap(parentIndex, index);
      index = parentIndex;
    }
  };

  const remove = () => {
    if (heap.length === 0) return null;
    if (heap.length === 1) return heap.pop();

    const root = heap[0];
    heap[0] = heap.pop();
    heapifyDown();
    return root;
  };

  const heapifyDown = () => {
    let index = 0;
    while (getLeftChildIndex(index) < heap.length) {
      let smallerChildIndex = getLeftChildIndex(index);
      const rightChildIndex = getRightChildIndex(index);

      if (rightChildIndex < heap.length && heap[rightChildIndex] < heap[smallerChildIndex]) {
        smallerChildIndex = rightChildIndex;
      }

      if (heap[index] <= heap[smallerChildIndex]) break;
      swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  };

  const peek = () => (heap.length > 0 ? heap[0] : null);
  const getHeap = () => [...heap];

  return { insert, remove, peek, getHeap };
};

const minHeap = createMinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);
minHeap.insert(2);

console.log(minHeap.getHeap()); // [1, 2, 8, 5, 3]
console.log(minHeap.remove()); // 1
console.log(minHeap.getHeap()); // [2, 3, 8, 5]
console.log(minHeap.peek()); // 2

최대 힙(Max Heap)

const createMaxHeap = () => {
  const heap = [];

  const getLeftChildIndex = (parentIndex) => 2 * parentIndex + 1;
  const getRightChildIndex = (parentIndex) => 2 * parentIndex + 2;
  const getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  const swap = (index1, index2) => {
    [heap[index1], heap[index2]] = [heap[index2], heap[index1]];
  };

  const insert = (value) => {
    heap.push(value);
    heapifyUp();
  };

  const heapifyUp = () => {
    let index = heap.length - 1;
    while (index > 0) {
      const parentIndex = getParentIndex(index);
      if (heap[parentIndex] >= heap[index]) break;
      swap(parentIndex, index);
      index = parentIndex;
    }
  };

  const remove = () => {
    if (heap.length === 0) return null;
    if (heap.length === 1) return heap.pop();

    const root = heap[0];
    heap[0] = heap.pop();
    heapifyDown();
    return root;
  };

  const heapifyDown = () => {
    let index = 0;
    while (getLeftChildIndex(index) < heap.length) {
      let largerChildIndex = getLeftChildIndex(index);
      const rightChildIndex = getRightChildIndex(index);

      if (rightChildIndex < heap.length && heap[rightChildIndex] > heap[largerChildIndex]) {
        largerChildIndex = rightChildIndex;
      }

      if (heap[index] >= heap[largerChildIndex]) break;
      swap(index, largerChildIndex);
      index = largerChildIndex;
    }
  };

  const peek = () => (heap.length > 0 ? heap[0] : null);
  const getHeap = () => [...heap];

  return { insert, remove, peek, getHeap };
};

const maxHeap = createMaxHeap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
maxHeap.insert(1);
maxHeap.insert(2);

console.log(maxHeap.getHeap()); // [8, 3, 5, 1, 2]
console.log(maxHeap.remove()); // 8
console.log(maxHeap.getHeap()); // [5, 3, 2, 1]
console.log(maxHeap.peek()); // 5