힙(Heap) 자료구조

1. 기초 지식

이진 트리:

n개의 노드로 구성된 트리 형태의 자료 구조로, 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.

포화 이진 트리:

각 레벨의 노드 수가 최대로 채워져 있는 이진 트리입니다. (마지막 레벨을 제외한 모든 레벨에서 노드들은 두 개의 자식을 가집니다)

완전 이진 트리:

각 레벨의 노드가 연속적으로 존재하는 이진 트리입니다. 마지막 레벨을 제외한 모든 레벨은 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워집니다.

참고: 포화 이진 트리는 완전 이진 트리의 특별한 형태입니다.

2. 정의

힙은 논리적으로 완전 이진 트리 형태를 가지며, 물리적으로는 연속된 메모리 공간(배열)에 저장됩니다. 모든 서브 트리에서 부모 노드가 자식 노드보다 크거나(최대 힘) 작은(최소 힘) 값을 가집니다. 루트 노드가 자식 노드보다 큰 경우를 최대 힘, 작은 경우를 최소 힘이라고 합니다.

참고: 아래 이미지는 최소 힘의 논리적 구조를 보여줍니다.

물리적 저장 구조:

보충: 힙에서 배열의 인덱스와 부모-자식 관계는 다음과 같습니다.

leftchild = 2 * parent + 1; rightchild = 2 * parent + 2;

rightchild = leftchild + 1; parent = (child - 1) / 2;

위 관계를 22, 33, 8의 인덱스로 예시를 통해 확인하면 이해를 높일 수 있습니다.

3. 인터페이스 (최소 힘 예시)

1. 노드 삽입 - push

먼저 요소를 배열의 끝에 추가합니다.
그 다음 부모 노드와 비교하며 필요시 교환을 반복합니다. 더 이상 교환이 불가능할 때 루프를 중단하고 삽입을 완료합니다.

참고: 논리적 구조는 아래와 같습니다.


void Push(const T& value)
{
    data.push_back(value);
    heapSize++;
    int currentIndex = data.size() - 1;
    int parentIndex = (currentIndex - 1) / 2;
    
    while (currentIndex != 0)
    {
        if (data[currentIndex] > data[parentIndex])
        {
            swap(data[currentIndex], data[parentIndex]);
            currentIndex = parentIndex;
            parentIndex = (currentIndex - 1) / 2;
        }
        else
            break;
    }
}

2. 노드 삭제 - pop

노드 삭제 = 첫 번째 요소 삭제

첫 번째 요소와 마지막 요소를 교환한 후 데이터 개수를 줄입니다(size).
새로운 첫 번째 요소를 계속해서 왼쪽 자식과 오른쪽 자식과 비교합니다. 왼쪽 또는 오른쪽 자식이 부모 노드보다 작을 경우 부모 노드와 해당 자식 노드를 교환합니다. 이 과정을 반복하며, 양쪽 자식 모두 부모보다 크거나 자식 노드가 없을 때 루프를 중단합니다.


void Pop()
{
    if (data.size() == 1)
    {
        data.pop_back();
        return;
    }
    
    swap(data[0], data[data.size() - 1]);
    data.pop_back();
    
    int parentIndex = 0;
    while (2 * parentIndex + 1 < data.size())
    {
        int leftChildIndex = 2 * parentIndex + 1;
        int rightChildIndex = leftChildIndex + 1;
        int smallestChildIndex = leftChildIndex;
        
        if (rightChildIndex < data.size())
        {
            if (data[rightChildIndex] > data[smallestChildIndex])
                smallestChildIndex = rightChildIndex;
        }
        
        if (data[smallestChildIndex] > data[parentIndex])
        {
            swap(data[smallestChildIndex], data[parentIndex]);
            parentIndex = smallestChildIndex;
        }
        else
            break;
    }
}

3. 힙 구축 - make_heap

i = (size-1-1)/2 노드부터 시작하여 계속해서 아래로 조정합니다.
아래로 조정: 현재 노드에서 시작하여 왼쪽 자식과 오른쪽 자식과 비교합니다. 부모 노드보다 작으면 교환하고, 계속해서 아래로 이 과정을 반복합니다. 더 이상 교환이 불가능할 때 루프를 중단합니다.
i--를 하여 전체 트리의 루트 노드(i=0)에 도달할 때까지 반복합니다.


void MakeHeap()
{
    int startIndex = (data.size() - 2) / 2;
    
    for (int i = startIndex; i >= 0; i--)
    {
        int currentIndex = i;
        bool shouldContinue = true;
        
        while (shouldContinue)
        {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = leftChildIndex + 1;
            int smallestChildIndex = currentIndex;
            
            if (leftChildIndex < data.size() && 
                data[leftChildIndex] > data[smallestChildIndex])
                smallestChildIndex = leftChildIndex;
                
            if (rightChildIndex < data.size() && 
                data[rightChildIndex] > data[smallestChildIndex])
                smallestChildIndex = rightChildIndex;
                
            if (smallestChildIndex != currentIndex)
            {
                swap(data[currentIndex], data[smallestChildIndex]);
                currentIndex = smallestChildIndex;
            }
            else
                shouldContinue = false;
        }
    }
}

4. 힙 정렬 - heap_sort

size번 pop을 반복합니다.

가장 작은 데이터를 size-1 위치에 두고 계속해서 --size를 하여 size가 0이 될 때까지 진행하면, 내림차순 배열을 얻을 수 있습니다.


void HeapSort()
{
    MakeHeap();
    
    int originalSize = data.size();
    for (int i = originalSize - 1; i > 0; i--)
    {
        swap(data[0], data[i]);
        heapSize--;
        
        int currentIndex = 0;
        while (2 * currentIndex + 1 < heapSize)
        {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = leftChildIndex + 1;
            int smallestChildIndex = leftChildIndex;
            
            if (rightChildIndex < heapSize && 
                data[rightChildIndex] > data[smallestChildIndex])
                smallestChildIndex = rightChildIndex;
                
            if (data[smallestChildIndex] > data[currentIndex])
            {
                swap(data[currentIndex], data[smallestChildIndex]);
                currentIndex = smallestChildIndex;
            }
            else
                break;
        }
    }
}

4. 요약

힙은 우리가 배우는 첫 번째 트리 형태의 자료 구조로, 나중에 배울 더 복잡한 트리 구조(이진 탐색 트리, AVL 트리 등)를 이해하는 데 중요한 기초 역할을 합니다. 힙의 부모-자식 관계와 관련 인터페이스는 힙을 학습하는 핵심 부분이며, 힙 정렬의 시간 복잡도는 O(logN)으로 삽입, 버블, 선택 정렬보다 훨씬 빠릅니다. 관심 있는 독자들은 더 깊이 이해해 보시길 권장합니다.

힙 자료 구조에 대한 모든 내용을 공유했습니다. 여러분께 도움이 되기를 바라며, 프로그래밍을 좋아하는 친구들과 함께 성장해 나가길 기대합니다.

태그: 자료구조 힙 이진트리 알고리즘 정렬

7월 19일 20:28에 게시됨

괴물 클럽