자료구조 힙(Heap)

이진 힙

이진 힙은 다음 특징(Properties)을 가진 이진 트리입니다.

1. 완전 트리(Complete Tree)이며 배열(Array)안에 저장되기 적합(Suitable)합니다.

2. 이진 힙은 최소(Min) 힙 또는 최대(Max) 힙 중 하나입니다. 최소 힙에서 루트 노드의 값은 모든 노드의 값중 가장 작은 값이며, 최대 힙에서 루트 노드의 값은 모든 노드의 값중 가장 큰 값입니다.

이진 힙의 표현

이진 힙은 완전 이진 트리(Complete Binary Tree)입니다. 이진 힙은 일반적으로(typically) 배열로 표현 됩니다.

루드 노드는 Arr[0] - 배열의 첫번째 요소가 됩니다.

부모 노드의 표현 - Arr[(i-1)/2] 

좌측 자식 노드의 표현 - Arr[(2*i)+1]

우측 자식 노드의 표현 - Arr[(2*i)+2]

이진 힙 배열의 순회 순서는 너비(Level) 순서입니다.

힙의 활용

1. 힙 정렬(Heap Sort) : 힙 정렬은 O(nLog n) 시간 복잡도를 가지는 배열의 정렬 방법입니다.

2. 우선순위 큐(Priority Queue) : 우선순위 큐는 O(log n)의 시간 복잡도를 가지는(삽입, 삭제 등)  이진 힙을 효율적으로 사용할 수 있습니다.

3. 그래프 알고리즘(Graph Algorithm) : 그래프 알고리즘에 우선순위 큐를 효과적으로 사용 할 수 있습니다.

최소 힙의 구현 - 소스코드(C++)

class MinHeap

{

    int *harr; // 힙 요소 포인터

    int capacity; // 최소 힙의 최대 크기

    int heap_size; // 최소 힙의 현재 크기

public:

    MinHeap(int capacity); // 생성자

 

    void MinHeapify(int);

    int extractMin(); 

    int parent(int i) { return (i-1)/2; } // 부모 노드 반환

    int left(int i) { return (2*i + 1); } // 좌측 자식 노드 반환

    int right(int i) { return (2*i + 2); } // 우측 자식 노드 반환

 

    void decreaseKey(int i, int new_val); 

 

    int getMin() { return harr[0]; } // 가장 작은 값(루트 노드) 반환

 

    void deleteKey(int i);

    void insertKey(int k);

};

 

MinHeap::MinHeap(int cap) // 생성자

{

    heap_size = 0;

    capacity = cap;

    harr = new int[cap];

}

 

void MinHeap::insertKey(int k) // 노드 추가

{

    if (heap_size == capacity)

    {

        cout << "\nOverflow: Could not insertKey\n";

        return;

    }

 

    heap_size++; // 사이즈 증가

    int i = heap_size - 1; 

    harr[i] = k;

 

    while (i != 0 && harr[parent(i)] > harr[i]) // 자신의 위치를 검색

    {

       swap(&harr[i], &harr[parent(i)]);

       i = parent(i);

    }

}

 

void MinHeap::decreaseKey(int i, int new_val)

{

    harr[i] = new_val;

    while (i != 0 && harr[parent(i)] > harr[i])

    {

       swap(&harr[i], &harr[parent(i)]);

       i = parent(i);

    }

}

 

int MinHeap::extractMin()

{

    if (heap_size <= 0)

        return INT_MAX;

    if (heap_size == 1)

    {

        heap_size--;

        return harr[0];

    }

 

    int root = harr[0];

    harr[0] = harr[heap_size-1];

    heap_size--;

    MinHeapify(0);

 

    return root;

}

 

void MinHeap::deleteKey(int i)

{

    decreaseKey(i, INT_MIN);

    extractMin();

}

 

void MinHeap::MinHeapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])

        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])

        smallest = r;

    if (smallest != i)

    {

        swap(&harr[i], &harr[smallest]);

        MinHeapify(smallest);

    }

}

정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.

질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.