[자료구조] - Heap(힙) 이해하기

참고 : https://yozm.wishket.com/magazine/detail/2312/

자료구조란?

데이터를 효율적으로 저장, 검색, 삭제할 수 있도록 설계된 구조나 방법

 

Heap(힙)

정렬, 우선순위 큐, 스케줄링과 같은 다양한 알고리즘에서 활용되는 자료구조

 

 

1. 정의

 

 완전 이진 트리  의 일종으로, 부모 노드 - 자식 노드 간 특정 조건을 만족하는 자료구조이다.

•  완전 이진 트리  란?
  • 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고
  • 마지막 Level을 제외한 모든 Level에 노드가 완전히 채워져 있는 구조

<출처 : https://yozm.wishket.com/magazine/detail/2312/>

 

 

2. 종류

 

 최대 힙 (Max-Heap)  과  최소 힙 (Min-Heap)  이 있다.

•  최대 힙 (Max-Heap)  이란?
  • 모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 갖는다.
  • 루트 노드는 전체 힙 중에서 가장 큰 값을 가지게 된다.

최대 힙 예시 <출처 : https://yozm.wishket.com/magazine/detail/2312/>

 

•  최소 힙 (Min-Heap)  이란?
  • 모든 부모 노드가 자식 노드보다 작거나 같은 값을 갖는다.
  • 루트 노드는 전체 힙 중에서 가장 작은 값을 가진다.

최소 힙 예시 <출처 : https://yozm.wishket.com/magazine/detail/2312/>

 

 

 

Heap 구현 예시

 

1. 힙 구현 방법

 

보통 배열을 이용해서 구현한다. 루트 노드 (9)는 배열의 첫 번째 인덱스에 위치하게 된다.

• 인덱스가 1부터 시작하는 배열의 경우
  • i 인덱스에 있는 노드의 왼쪽 자식 노드는 2 x i 인덱스에 위치
  • i 인덱스에 있는 노드의 오른쪽 자식 노드는 2 x i + 1 인덱스에 위치

힙 구현 방법 <출처 : https://yozm.wishket.com/magazine/detail/2312/>

 

• 루트 노드 (9) 의 인덱스가 1이기 때문에
  • 왼쪽 자식 노드 (8) 의 인덱스는 2 x 1 = 2 가 되고
  • 오른쪽 자식 노드 (6) 의 인덱스는 2 x 1 + 1 = 3 이 된다.

 

 

Heap 구현 코드 예시 (C++ 표준 라이브러리 사용)

<algorithm> 헤더에 정의되어 있는 make_heap, push_heap, pop_heap 함수들을 사용하면 쉽게 Heap을 구현할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 초기 데이터를 가진 벡터 생성
    vector<int> v = {20, 15, 30, 5, 10};

    // 벡터를 최대 힙으로 만듦
    make_heap(v.begin(), v.end());

    // 새로운 요소를 추가하고 힙을 재구성
    v.push_back(35);
    push_heap(v.begin(), v.end());

    // 힙의 최대 요소(루트) 제거
    pop_heap(v.begin(), v.end());
    v.pop_back();

    // 힙의 요소 출력 (힙 순서대로 출력되지는 않음)
    cout << "Heap elements: ";
    for (int i : v)
        cout << i << " ";
    cout << endl;

    return 0;
}

 

다음과 같은 과정들을 거친다.

 

1. 벡터를 생성하고 초기 데이터로 채웁니다.
2. make_heap 함수를 사용하여 벡터를 최대 힙으로 변환합니다.
3. 새로운 요소를 벡터에 추가한 후 push_heap으로 힙을 재조정합니다.
4. pop_heap을 사용하여 힙의 최대 요소를 제거합니다. 이 함수는 힙의 최대 요소를 벡터의 끝으로 이동시킨 후, 나머지 벡터 요소로 힙을 재구성합니다. pop_back 메서드를 호출하여 실제로 요소를 제거합니다.

 

힙을 실제로 구현하는 것보다 훨씬 빠르고 쉽고 효율적이다.