Heap (최소 힙)

박채윤·2024년 12월 18일
알고리즘자료구조
1

✨들어가면서...

하루에 한 문제 이상 코테문제를 풀려고 도전중인데 처음으로 heap에 관한 문제로 들어오게됐다.

heap이란 무엇인지..? 어떤 장점이 있어서 언제 사용해야하는지, 또한 어떻게 구현해야 하는지 알아보자.

heap에 관해서 하나도 모르는 상태에서 첫 문제를 풀기까지 알아봤던 과정대로 설명해보려 한다.

Heap

heap 이란?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 특정 조건을 만족하는 자료구조이다. 힙의 종류에는 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있으며, 그 차이는 부모 노드와 자식 노드 간의 값 관계에 있다.

우선 heap에 관한 설명을 찾아본 결과 다음과 같은 정보를 얻을 수 있었다.

완전이진트리..? 최소 힙? 최대 힙?
이것들이 뭔지 모른채로 문제를 풀 수 없기에 하나씩 알아보자.

완전 이진트리?

완전 이진트리란, 모든 레벨이 가득 차 있어야 하며, 마지막 레벨을 제외한 모든 레벨이 왼쪽부터 차례대로 채워진 이진 트리를 의미한다.
즉, 트리의 마지막 레벨에서만 빈 노드가 있을 수 있으며, 그 빈 노드들은 오른쪽부터 차례대로 빈 자리가 나온다.

힙은 항상 완전이진트리 형태로 구성되어 있어야 하며, 이를 통해 빠른 삽입과 삭제가 가능하다.

이렇게 이진트리로 이루어졌기 때문에 heap자료구조에서 시간복잡도는 O(logN)을 유지할 수 있다고 한다.

어떻게 O(logN)을 유지하지..? 라는 궁굼증이 여기서 생겼는데 뒤에서 자세히 알아보자.

최소 힙, 최대 힙에 대해 알아보기 전에...

  • 힙 자료구조의 동작원리

    힙 자료구조는 기본적으로 삽입(Insert)과 삭제(Extract) 연산을 통해 동작한다. 이때, 최소 힙(Min Heap)과 최대 힙(Max Heap)의 동작 원리는 부모 노드와 자식 노드 간의 값을 비교하는 방식에서 차이가 난다.

삽입과 삭제를 해야하는 문제가 있다? ==>heap을 떠올려 볼 수 있을것 같다.

어떻게 삽입, 삭제하길래 heap자료구조를 사용하는 걸까?

최소 힙

heap자료구조는 위에서 봤던것 처럼 완전 이진트리 구조로 되어있다.

그렇다면 최소 힙은?

부모 노드의 값이 항상 자식 요소의 값보다 작은 tree구조이다.
따라서 heap의 루트 노드(최상위 노드) 는 항상 가장 작은 값을 가지게 된다.

  • 값을 삽입할 경우

    값을 삽입할 때는, 새로운 값을 리프 노드(가장 마지막)에 추가한 뒤, 부모와 비교하면서 위로 올라가며(Heapify Up) 힙의 특성을 유지한다.

  • 값을 삭제할 경우

    최소 힙에서 삭제하는 연산은 항상 루트 노드의 값을 삭제하는 방식이다. 삭제된 후, 트리의 구조를 다시 힙 속성에 맞게 재조정해야 한다. 이 과정은 Heapify Down이라고 불립니다.

삽입, 삭제, 두가지 경우 모두 부모 노드 <==> 자식 노드들 간의 비교를 반복하며 이뤄진다는 공통점이 있다.

삽입만 예를 들어보자면

예시
현재 힙: [10, 15, 20, 17] 

      10
    /   \
  15     20
 /
 17

삽입 값: 5
새로운 상태: 5는 리프 노드로 삽입되고, 부모인 10과 비교하여 위치를 바꿔 올라간다.
결과적으로:

    5
   / \
 10   20
 /      \
15      17

앞서 언급한 것처럼 부모 노드 <==> 자식 노드들의 비교만 위쪽 방향으로 계속해서 수행을 하게되고 이로 인해 O(logN)이라는 비교적 효과적인 시간 복잡도를 얻을 수 있는 것이다.

최대 힙

최소 힙과 반대되는 구조로 생각하면 되기때문에 생략한다..

Heapify Down , Heapify Up

앞서 살펴본 내용을 바탕으로 정리를 해보면

  • 1.heap은 이진 트리구조
    1. 최소 힙, 최대 힙 이 존재한다.
    1. 삽입과 삭제과정은 부모노드 <==> 자식노드의 비교로 순차적으로 이뤄진다.

3번의 과정을 수행하는 동작이 바로 heapifyDown , heapifyUp 이다.

     1
   /  \
  2    3

각 레벨에서 다음과 같은 삼각형 형태의 부모, 자식 노드의 비교가 이뤄지게 되는데 그것을 수행하는 것을 heapifyDown , heapifyUp 이라고 한다.

heapifyDown : 삭제 과정에서 최상위 노드를 제거 후 마지막 요소를 최상위 요소에 배치후, 아래로 순차적으로 부모<==>자식 노드의 비교가 이뤄짐

heapifyUp: 삽입 과정에서 리프 노드부터 위쪽 방향으로 순차적으로 부모<==>자식 노드의 비교가 이뤄짐

우선순위 큐

구현 전에 마지막으로 알아야 할 것이 우선순위 큐이다.

일반적으로 큐 라고한다면 선입선출(LIFO)구조를 가진 것으로 알고있었는데 우선순위 큐는 무엇이지??

우선순위 큐는 일반적인 큐와는 다르게, 큐에 삽입된 각 요소가 우선순위를 가짐에 따라 처리 순서가 결정된다.
기본 큐는 선입선출(FIFO) 방식에 따라 먼저 들어온 요소부터 처리하지만,
우선순위 큐에서는 우선순위가 높은 요소부터 먼저 처리된다. 이때 우선순위는 숫자나 값에 따라 정해지며, 우선순위 큐에 삽입된 항목들은 우선순위에 맞게 정렬되거나, 우선순위가 높은 항목이 가장 먼저 꺼내진다.

여기서 드는 의문은 우선순위 큐 와 힙은 무슨 관계가 있냐는 것이다.

우선순위 큐는 우선순위에 따라서 어떤 일을 수행하게 되고 이러한 동작이
최대 힙 or 최소 힙의 자료구조와 딱 맞아 떨어진다는 것이다.

즉, 우선순위 큐는 힙 자료구조를 사용하여 구현하는 것이 가장 적합하다.

JS로 구현 해보자(최소 힙)

코테 문제를 풀기위해서 검색해본 결과 js에서는 heap자료구조를 직접 구현해야 한다고 했다. 앞선 설명들을 바탕으로 직접 구현 해보자.

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

  // 부모 인덱스 계산
  const getParentIndex = (index) => Math.floor((index - 1) / 2)
  // 왼쪽 자식 인덱스 계산
  const getLeftChildIndex = (index) => index * 2 + 1
  // 오른쪽 자식 인덱스 계산
  const getRightChildIndex = (index) => index * 2 + 2

  // 값을 삽입하고 최소 힙을 유지
  const insert = (value) => {
    heap.push(value)
    heapifyUp()
  }
  const swap = (el1, el2) => ([heap[el1], heap[el2]] = [heap[el2], heap[el1]])
  // 최소값을 추출하고 최소 힙을 유지
  const extractMin = () => {
    if (heap.length === 0) return null
    if (heap.length === 1) return heap.pop()

    const min = heap[0]
    heap[0] = heap.pop() // 마지막 값을 루트로 이동
    heapifyDown()
    return min
  }

  // 삽입 시 힙 속성 유지
  const heapifyUp = () => {
    let index = heap.length - 1
    while (index > 0) {
      const parentIndex = getParentIndex(index)
      if (heap[index] >= heap[parentIndex]) break
      swap(index, parentIndex)
      index = parentIndex
    }
  }

  // 추출 시 힙 속성 유지
  const heapifyDown = () => {
    let index = 0
    const length = heap.length

    while (getLeftChildIndex(index) < length) {
      const leftChildIndex = getLeftChildIndex(index)
      const rightChildIndex = getRightChildIndex(index)
      let smallerChildIndex = leftChildIndex

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

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

  return { insert, extractMin, heap }
}

1. 최소 힙을 정의 해주자.

const createMinHeap = ()=>{
  const heap = [] // 자료들을 넣기위한 heap 정의
  const insert = ()=>{} // 자료들의 삽입을 담당
  const extractMin = ()=>{} // 자료들의 삭제를 담당
  const heapifyDown = ()=>{} // 최소힙 구조를 유지시켜줄 함수
  const heapifyUp = ()=> {} // 최소힙 구조를 유지시켜줄 함수
  const 나머지 필요한 함수들 ()=>{}
}

최소힙을 생성해줄 함수를 정의하고 해당 함수의 구성요소는 위와 같다.

앞서 설명한 것처럼 insert 과정에는 heapifyUp(위로 올라가면서 비교) 함수가 실행되며 최소 힙 구조를 유지해줄 것이고,

extarct 과정에는 heapifyDown(아래로 내려가며 비교) 함수가 실행되며 최소 힙 구조를 유지해 줄 것이다.

2. heapifyUp(삽입)

const heapifyUp = ()=>{
  let index = heap.length -1 // 삽입과정은 리프 노드부터 시작하기 때문
  
  while(index > 0){
   const parentIndex =  getParentIndex(index) // Math.floor((index - 1) / 2)
   if(heap[index] >= heap[parentIndex]) break
   // 자식요소가 부모요소보다 크다면 최소힙 만족 그자리에 위치
    
   swap(index,parentIndex) // swap을 통해 두 노드의 값을 교환 
   index = parentIndex 
   // 최소 힙 조건을 만족하지 못했다면 index를 부모 인덱스로 교환후 while문 재 실행 
  }
}

삽입 과정에서 일어나는 heapifyUp과정이다

heap구조의 리프노드에 새로운값을 넣어주고 부모 노드와의 비교를 이어가며 최소 힙 구조를 만족시켜준다.

이렇게 정의한 heapifyUp함수는 삽입 과정이기에 insert() 내부에서 호출만 해주면된다.

3.insert

 const insert = (value) => {
    heap.push(value) // 새로운 값을 배열의 마지막(리프노드)에 삽입
    heapifyUp() // heapifyUp 과정을 통해 최소 힙 조건 만족
  }

새로운 요소를 삽입(리프 노드에) 할 때마다 앞서 정의한 heapifyUp()을 실행 시켜주면서 최소 힙 구조를 유지한다.

4.heapifyDown

const heapifyDown = () => {
    let index = 0 // 삭제 과정은 최상위 노드 부터 실행된다.
    const length = heap.length

    while (getLeftChildIndex(index) < length) {
   // 현재 노드의 왼쪽 자식 노드가 힙의 범위 내에 있는지 확인
  // 왼쪽 자식이 존재하면 계속해서 힙의 구조를 유지하기 위한 비교 작업을 진행
      
      const leftChildIndex = getLeftChildIndex(index) //전체코드에 나와있음
      const rightChildIndex = getRightChildIndex(index)
      let smallerChildIndex = leftChildIndex

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

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

heapifyUp과 비교해서 조금 복잡해 보일 수 있지만 코드를 따라가보면 앞서 설명한 개념과 일치한 동작을 확인 할 수있다.

5.extractMin


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

    const min = heap[0]
    heap[0] = heap.pop() // 마지막 값을 루트로 이동
    heapifyDown()
    return min
  }

앞서 본것 처럼 삭제 과정에는 heapifyDown() 함수를 실행해서 최소 힙 자료구조를 유지해 준다.

마무리

이렇게 힙 자료구조에 대해 알아보았다.
힙은 최소값 또는 최대값을 빠르게 추출할 수 있는 특성 덕분에 우선순위 큐와 같은 상황에서 유용하다.

최소 힙은 최소값을 먼저 처리해야 할 때, 최대 힙은 최대값을 먼저 처리해야 할 때 적합하다. 또한, K개의 최소값/최대값을 구하는 문제, 힙 정렬, 실시간 데이터 스트림 처리 등에서 효율적으로 활용된다.

이러한 특성을 기억하고, 필요할 때 적합한 힙 자료구조를 적용하면 문제 해결에 큰 도움이 될 것같다.

profile
박채윤
왕이될 상인가
이전 포스트

Next.js 더 잘 사용해보기(Routing)

0개의 댓글