최소 힙 이진 트리

최소 힙 이진 트리는 루트 노드가 트리에서 최소 키를 갖는 이진 트리입니다.

위의 정의는 트리의 모든 하위 트리에 적용됩니다. 이를 최소 힙 속성이라고 합니다.

마지막 두 레이어를 제외한 거의 모든 노드에는 두 개의 자식이 있어야 합니다. 즉, 이것은 마지막 2개의 레이어를 제외하고는 거의 완전한 이진 트리입니다.

아래 트리는 위의 두 속성이 유지되므로 최소 힙 이진 트리의 예입니다.

이제 최소 힙 트리가 무엇인지 살펴봤으니 어떻게 표현할 수 있는지 살펴보겠습니다.

최소 힙 트리의 표현

최소 힙 이진 트리는 일반적으로 배열로 표시되며 아래 형식에 따라 인덱싱됩니다.

전체 트리의 루트는 arr[0]에 있습니다.

아래 그림과 같이 인덱싱을 사용합니다. 위의 표와 일치하는 패턴을 여기서 찾는 것은 그리 어렵지 않습니다.

이 인덱싱은 이진 트리의 수준 순서 순회를 따르므로 이진 힙 배열은 수준 순서 순회를 사용하는 이진 트리입니다.

위의 그림은 Min Heap Tree의 배열 표현을 보여줍니다.

이제 개념을 다뤘으니 이를 C로 구현해 봅시다!

최소 힙 트리 구현

배열 표현을 사용하여 트리를 만들 것입니다. Min Heap의 구조 작성을 시작하겠습니다.

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // Current Size of the Heap
    int size;
    // Maximum capacity of the heap
    int capacity;
};

요소의 배열과 요소가 삽입되거나 삭제될 때 업데이트되는 크기가 있습니다.

어레이에는 어레이의 최대 크기를 나타내는 용량도 있습니다.

부모와 자식을 찾는 것과 같이 최소 힙 트리를 나타내고 있음을 나타내기 위해 작성해야 하는 몇 가지 함수가 있습니다.

int parent(int i) {
    // Get the index of the parent
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    // Return the root node element,
    // since that's the minimum, by the min-heap
    // property
    return heap->arr[0];
}

힙을 초기화하고 해제하는 함수를 작성할 것입니다.

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
    minheap->arr = (int*) calloc (capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

이제 요소를 삽입하는 방법으로 넘어갑시다!

최소 힙에 삽입

삽입 알고리즘은 간단합니다. 그러면 트리에 요소가 삽입됩니다.

알고리즘 분석:

• 첫째, 항상 트리의 맨 아래에 삽입하십시오. 삽입된 요소의 초기 위치는 마지막 레벨입니다.
• 이제 최소 힙 속성이 충족되도록 이 요소의 위치를 업데이트해야 합니다.
• 모든 하위 트리의 루트 노드는 최소여야 하므로 직계 부모의 하위 트리를 확인합니다.
• 부모가 이 삽입된 요소보다 크면 교체하여 위치를 업데이트해야 합니다.
• 하지만 아직 완료되지 않았습니다. 업데이트된 노드의 하위 트리에서 최소 힙 속성을 위반할 수 있기 때문입니다!
• 루트 노드에 도달할 때까지 계속 스와핑해야 합니다. 그 후에 작업이 완료됩니다.

이 절차를 이해하기 위해 예를 들어 보겠습니다.

요소가 하나만 있는 아래 트리를 고려하십시오.

요소 40을 삽입합시다. 요소가 하나뿐이므로 맨 아래에 삽입하고 10 < 40이므로 min-heap 속성이 만족됨을 관찰합니다. 따라서 스왑할 필요가 없습니다.

다음으로 50을 삽입합니다. 유사한 절차가 이어집니다.

다음으로 5를 삽입합니다. 이제 먼저 트리의 맨 아래 인덱스 3에 삽입합니다.

최소 힙 속성은 하위 트리 1-3에 대해 위반되므로 전체 트리에 대해 위반됩니다. 따라서 루트에 도달할 때까지 부모와 계속 교체해야 합니다.

따라서 노드 0에 뿌리를 둔 하위 트리에 대해 최소 힙 속성이 위반되기 때문에 스왑이 한 번 더 필요합니다.

괜찮은. 이제 시각화했으므로 작성해 봅시다!

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // Inserts an element to the min heap
    // We first add it to the bottom (last level)
    // of the tree, and keep swapping with it's parent
    // if it is lesser than it. We keep doing that until
    // we reach the root node. So, we will have inserted the
    // element in it's proper position to preserve the min heap property
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    // We can add it. Increase the size and add it to the end
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // Keep swapping until we reach the root
    int curr = heap->size - 1;
    // As long as you aren't in the root node, and while the 
    // parent of the last element is greater than it
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        // Swap
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        // Update the current index of element
        curr = parent(curr);
    }
    return heap; 
}

이제 삭제 방법을 구현할 것입니다.

최소 힙에서 삭제

인덱스 요소 삭제를 살펴보기 전에 최소 힙이 루트와 매우 밀접하게 연관되어 있으므로 먼저 루트 삭제를 살펴보겠습니다.

최소 요소(즉, 루트)를 삭제하려면 다음을 수행합니다.

• 배열(트리)의 마지막 요소로 루트 업데이트
• 이제 하단의 마지막 요소를 제거합니다. 이것은 마지막에 교체 및 삭제와 유사합니다! 더 이상 루트 값에 신경 쓰지 않기 때문에 대신 업데이트하기만 하면 됩니다.
• 다시 문제는 min-heap 속성을 유지해야 한다는 것입니다.
• 따라서 전체 트리가 이 속성을 유지하도록 해야 합니다. 이를 위해 heapify()라는 함수를 사용할 것입니다.

따라서 heapify() 메서드도 수행해야 삭제 메서드가 완료된다는 것을 알 수 있습니다.

MinHeap* delete_minimum(MinHeap* heap) {
    // Deletes the minimum element, at the root
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // Update root value with the last element
    heap->arr[0] = last_element;

    // Now remove the last element, by decreasing the size
    heap->size--;
    size--;

    // We need to call heapify(), to maintain the min-heap
    // property
    heap = heapify(heap, 0);
    return heap;
}

heapify() 절차

이 함수는 요소 인덱스 index를 가져오고 바로 하위 트리의 가장 작은 요소와 교체하여 최소 힙 속성을 유지합니다.

결과 트리는 최소 힙 속성을 충족합니다.

여기에는 하위 트리의 최소 요소 찾기 및 현재 요소와의 교체 수행이 포함됩니다.

이후에도 전체 트리가 이를 만족하는지 확인해야 합니다. 따라서 루트에 도달할 때까지 가장 작은 요소에 대해 프로시저를 재귀적으로 호출해야 합니다!

MinHeap* heapify(MinHeap* heap, int index) {
    // Rearranges the heap as to maintain
    // the min-heap property
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // Variable to get the smallest element of the subtree
    // of an element an index
    int smallest = index; 
    
    // If the left child is smaller than this element, it is
    // the smallest
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // Similarly for the right, but we are updating the smallest element
    // so that it will definitely give the least element of the subtree
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // Now if the current element is not the smallest,
    // swap with the current element. The min heap property
    // is now satisfied for this subtree. We now need to
    // recursively keep doing this until we reach the root node,
    // the point at which there will be no change!
    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

이제 이 delete_minimum() 함수를 확장하여 모든 요소를 삭제할 수 있습니다.

임의 요소 삭제

여기에는 원하는 요소를 가능한 최소값으로 설정하는 것만 포함됩니다. 즉, 현재 최소값보다 작아야 하므로 get_min() - 1이 됩니다.

이제 새로운 루트가 이 요소가 되도록 위치를 업데이트할 때까지 계속 교체합니다.

이제 이전 delete_minimum() 함수로 돌아왔습니다! 새 루트를 간단히 삭제할 수 있습니다!

이를 통해 전체 삭제 절차는 다음과 같습니다.

MinHeap* delete_element(MinHeap* heap, int index) {
    // Deletes an element, indexed by index
    // Ensure that it's lesser than the current root
    heap->arr[index] = get_min(heap) - 1;
    
    // Now keep swapping, until we update the tree
    int curr = index;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }

    // Now simply delete the minimum element
    heap = delete_minimum(heap);
    return heap;
}

휴! 드디어 끝났습니다. 이제 트리를 시각화하기 위해 print() 함수와 함께 지금까지의 전체 코드를 보여드리겠습니다.

완전한 코드

#include <stdio.h>
#include <stdlib.h>

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // Current Size of the Heap
    int size;
    // Maximum capacity of the heap
    int capacity;
};

int parent(int i) {
    // Get the index of the parent
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    // Return the root node element,
    // since that's the minimum
    return heap->arr[0];
}

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
    minheap->arr = (int*) calloc (capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // Inserts an element to the min heap
    // We first add it to the bottom (last level)
    // of the tree, and keep swapping with it's parent
    // if it is lesser than it. We keep doing that until
    // we reach the root node. So, we will have inserted the
    // element in it's proper position to preserve the min heap property
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    // We can add it. Increase the size and add it to the end
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // Keep swapping until we reach the root
    int curr = heap->size - 1;
    // As long as you aren't in the root node, and while the 
    // parent of the last element is greater than it
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        // Swap
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        // Update the current index of element
        curr = parent(curr);
    }
    return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
    // Rearranges the heap as to maintain
    // the min-heap property
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // Variable to get the smallest element of the subtree
    // of an element an index
    int smallest = index; 
    
    // If the left child is smaller than this element, it is
    // the smallest
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // Similarly for the right, but we are updating the smallest element
    // so that it will definitely give the least element of the subtree
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // Now if the current element is not the smallest,
    // swap with the current element. The min heap property
    // is now satisfied for this subtree. We now need to
    // recursively keep doing this until we reach the root node,
    // the point at which there will be no change!
    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

MinHeap* delete_minimum(MinHeap* heap) {
    // Deletes the minimum element, at the root
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // Update root value with the last element
    heap->arr[0] = last_element;

    // Now remove the last element, by decreasing the size
    heap->size--;
    size--;

    // We need to call heapify(), to maintain the min-heap
    // property
    heap = heapify(heap, 0);
    return heap;
}

MinHeap* delete_element(MinHeap* heap, int index) {
    // Deletes an element, indexed by index
    // Ensure that it's lesser than the current root
    heap->arr[index] = get_min(heap) - 1;
    
    // Now keep swapping, until we update the tree
    int curr = index;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }

    // Now simply delete the minimum element
    heap = delete_minimum(heap);
    return heap;
}

void print_heap(MinHeap* heap) {
    // Simply print the array. This is an
    // inorder traversal of the tree
    printf("Min Heap:\n");
    for (int i=0; i<heap->size; i++) {
        printf("%d -> ", heap->arr[i]);
    }
    printf("\n");
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

int main() {
    // Capacity of 10 elements
    MinHeap* heap = init_minheap(10);

    insert_minheap(heap, 40);
    insert_minheap(heap, 50);
    insert_minheap(heap, 5);
    print_heap(heap);
    
    // Delete the heap->arr[1] (50)
    delete_element(heap, 1);

    print_heap(heap);
    free_minheap(heap);
    return 0;
}

산출

Min Heap:
5 -> 50 -> 40 -> 
Min Heap:
5 -> 40 -> 

구현의 시간 복잡도

위 절차의 시간 복잡도는 다음과 같습니다.

코드 다운로드

내가 업로드한 Github Gist로 전체 코드를 다운로드할 수 있습니다. 이와 관련하여 질문이 있으시면 아래 댓글 섹션에서 질문하십시오!

결론

이 기사에서 우리는 Min Heap Binary Tree를 표현하는 방법과 C로 구현하는 방법을 배웠습니다.

참조

• Cormen의 힙 그림
• 이진 힙에 대한 Wikipedia 기사