자료구조 - 히프

[히프]

히프(heap)는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조입니다.

간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리입니다.

key(부모노드) >= key(자식노드)

 

히프 트리에서는 중복 값을 허용한다는 것을 유의해야 합니다.

 

 

히프의 종류

최대 히프(max heap) : 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다.
최소 히프(min heap) : 부모 노드의 키값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다.

 

 

 

히프의 구현

히프는 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙여서 배열의 인덱스에 넣을 수 있습니다.

프로그램 구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지 않습니다.

 

 

 

히프의 부모와 자식 관계에 대해서 알아보겠습니다.

부모 노드 인덱스: (i - 1) / 2
왼쪽 자식 노드 인덱스: (i * 2) + 1
오른쪽 자식 노드 인덱스: (i * 2) + 2

 

 

 

[히프의 삽입과 삭제 연산]

 

삽입 연산

1. 새로운 요소를 힙의 마지막 위치에 삽입합니다.

2. 새로운 요소를 올바른 위치로 이동시키기 위해 상향 조정을 수행합니다 (sift-up).

 

 

void insert(int data) 
{
    // 새로운 데이터를 힙의 마지막 위치에 삽입
    heap.push_back(data);
    
    // 상향 조정을 통해 힙 속성 유지
    siftUp(heap.size() - 1);
}

void siftUp(int index) 
{
    while (index > 0) 
    {
        int parent = (index - 1) / 2;
        
        // 부모 노드가 현재 노드보다 크면 힙 속성 유지
        if (heap[index] <= heap[parent]) 
        {
            break;
        }
        
        // 현재 노드와 부모 노드 교환
        std::swap(heap[index], heap[parent]);
        index = parent;
    }
}

 

 

 

삭제 연산

1. 루트 노드를 제거하고, 힙의 마지막 요소를 루트로 이동시킵니다.

2. 루트 노드를 올바른 위치로 이동시키기 위해 하향 조정을 수행합니다 (sift-down).

void deleteMax() 
{
    if (heap.empty()) 
    {
        throw std::runtime_error("Queue is empty");
    }
    
    // 루트 노드와 마지막 노드를 교환
    std::swap(heap.front(), heap.back());
    
    // 마지막 노드 제거
    heap.pop_back();
    
    // 하향 조정을 통해 힙 속성 유지
    siftDown(0);
}

void siftDown(int index) 
{
    int size = heap.size();
    while (true) 
    {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        // 왼쪽 자식이 현재 노드보다 크면 largest 갱신
        if (left < size && heap[left] > heap[largest]) 
        {
            largest = left;
        }
        
        // 오른쪽 자식이 현재 노드보다 크면 largest 갱신
        if (right < size && heap[right] > heap[largest]) 
        {
            largest = right;
        }
        
        // 힙 속성이 유지되면 루프 종료
        if (largest == index) 
        {
            break;
        }
        
        // 현재 노드와 largest 노드 교환
        std::swap(heap[index], heap[largest]);
        index = largest;
    }
}

 

 

 

 

히프 구현 전체 코드

#include <iostream>
#include <vector>
#include <stdexcept>

class PriorityQueueHeap 
{
    public:
        void insert(int data) 
        {
            // 새로운 데이터를 힙의 마지막 위치에 삽입
            heap.push_back(data);
        
            // 상향 조정을 통해 힙 속성 유지
            siftUp(heap.size() - 1);
        }

        void deleteMax() 
        {
            if (heap.empty()) 
            {
                throw std::runtime_error("Queue is empty");
            }
        
            // 루트 노드와 마지막 노드를 교환
            std::swap(heap.front(), heap.back());
            
            // 마지막 노드 제거
            heap.pop_back();
        
            // 하향 조정을 통해 힙 속성 유지
            siftDown(0);
        }

        int peekMax() 
        {
            if (heap.empty()) 
            {
                throw std::runtime_error("Queue is empty");
            }
            // 힙의 루트 노드 반환
            return heap.front();
        }        

    private:
        std::vector<int> heap;    

        void siftUp(int index) 
        {
            while (index > 0) 
            {
                int parent = (index - 1) / 2;
                
                // 부모 노드가 현재 노드보다 크면 힙 속성 유지
                if (heap[index] <= heap[parent])
                {
                    break;
                }
            
                // 현재 노드와 부모 노드 교환
                std::swap(heap[index], heap[parent]);
                index = parent;
            }
        }

        void siftDown(int index)
        {
            int size = heap.size();
            while (true) 
            {
                int largest = index;
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                // 왼쪽 자식이 현재 노드보다 크면 largest 갱신
                if (left < size && heap[left] > heap[largest]) 
                {
                    largest = left;
                }
                
                // 오른쪽 자식이 현재 노드보다 크면 largest 갱신
                if (right < size && heap[right] > heap[largest]) 
                {
                    largest = right;
                }
                
                // 힙 속성이 유지되면 루프 종료
                if (largest == index) 
                {
                    break;
                }
                
                // 현재 노드와 largest 노드 교환
                std::swap(heap[index], heap[largest]);
                index = largest;
            }
        }
};    

int main()
{
    PriorityQueueHeap pq;
    pq.insert(3);
    pq.insert(5);
    pq.insert(1);

    std::cout << "Max: " << pq.peekMax() << std::endl; // 5
    pq.deleteMax();
    std::cout << "Max after delete: " << pq.peekMax() << std::endl; // 3

    return 0;
}