[Data Structures] Heap (힙)

Priority Queue (우선순위 큐)

  우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료 구조이다. 우선 순위 큐는 배열이나 연결 리스트로 구현할 수 있지만 데이터의 수가 많아지면 노드의 수에 비례해서 성능이 저하되기 때문에 가장 좋은 성능을 이끌어 내기 위한 힙이라는 자료구조를 사용한다.

 

Heap (힙)

  힙은 완전 이진 트리이다. Max Heap(최대 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같고, Min Heap(최소 힙)은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 작거나 같다.

 

- 이진 힙의 구조

 

  힙은 완전 이진 트리 이기 때문에 원소가 배열에 저장된다.

 

- Insertion

  원소를 삽입할 때에는 트리 마지막에 삽입을 한 후, 우선순위가 부모 노드보다 높다면 자리를 바꾸며 올라간다.

  시간 복잡도 : O(logN)

 

- DeleteMin

ex1)

ex2)

ex3)

  우선순위가 가장 높은 노드(루트 노드)를 삭제할 때는, 루트 노드를 비우고, 빈 노드를 {왼쪽 자식 노드, 오른쪽 자식 노드, 트리의 마지막 노드} 중에서 가장 우선순위가 높은 값으로 채운다.

시간 복잡도 : O(logN)

 

-BuildHeap

  일반적인 완전 이진 트리를 힙으로 만드는 과정이다.

  트리의 1레벨 부터 자식 노드와 우선 순위 정렬이 시작된다.

 

  h = logN일 때,

  1레벨은 2^(h - 1)개의 노드가 있고 각 노드들이 최대 1급간 내려간다. -> 2^(h - 1) * 1

  2레벨은 2^(h - 2)개의 노드가 있고 각 노드들이 최대 2급간 내려간다. -> 2^(h - 2) * 2

  ...

  h - 1레벨은 2^(1)개의 노드가 있고, 각 노드들이 최대 (h - 1)급간 내려간다. -> 2^(1) * (h - 1)

  h 레벨에는 1개의 노드가 있고, 이 노드는 최대 h급간 내려간다. -> 2^(0) * h

 

  모든 계산을 합하면

  S = 2*2^(logN) - logN - 2 <= 2N으로 정리가 되기 때문에 

  완전 이진 트리를 힙으로 만드는 동작의 시간 복잡도는 O(N)이다.

Implementation

다음은 Min Heap의 ADT이다.

typedef struct HeapStruct *Heap;
struct HeapStruct
{
    int capacity;
    int size;
    int *elements;
};

Heap CreateHeap(int heapSize);
void Insert(Heap heap, int value);
int Find(Heap heap, int value);
void DeleteMin(Heap heap);
void printHeap(Heap heap);
void FreeHeap(Heap heap);

 

다음은 Min Heap의 구현체이다.

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

Heap CreateHeap(int heapSize)
{
    Heap heap = (Heap)malloc(sizeof(struct HeapStruct));

    heap->capacity = heapSize;
    heap->size = 0;
    heap->elements = (int *)malloc(sizeof(int) * (heap->capacity));
    heap->elements[0] = -2147483648;

    return heap;
}

void Insert(Heap heap, int value)
{
    int i;
    if (heap->size == heap->capacity)
    {
        printf("Insertion Error: Min Heap is full.\n");
    }
    else if (Find(heap, value))
    {
        printf("%d is already in the heap.\n", value);
    }
    else
    {
        for (i = ++(heap->size); heap->elements[i / 2] > value; i /= 2)
        {
            heap->elements[i] = heap->elements[i / 2];
        }
        heap->elements[i] = value;
        printf("Insert %d\n", value);
    }
}

int Find(Heap heap, int value)
{
    for (int i = 1; i <= heap->size; i++)
    {
        if (heap->elements[i] && heap->elements[i] == value)
            return 1;
    }
    return 0;
}

void DeleteMin(Heap heap)
{
    if (heap->size == 0)
    {
        printf("Deletion Error: Min Heap is empty!\n");
    }
    else
    {
        int i, Child;
        int MinElement, LastElement;

        MinElement = heap->elements[1];
        LastElement = heap->elements[(heap->size)--];

        for (i = 1; i * 2 <= heap->size; i = Child)
        {
            Child = i * 2;
            if (Child != heap->size && heap->elements[Child + 1] < heap->elements[Child])
                Child++;

            if (LastElement > heap->elements[Child])
                heap->elements[i] = heap->elements[Child];
            else
                break;
        }
        heap->elements[i] = LastElement;

        printf("Min element(%d) deleted.\n", MinElement);
    }
}

void printHeap(Heap heap)
{
    if (heap->size == 0)
        printf("Min Heap is empty!\n");
    else
    {
        for (int i = 1; i <= heap->size; i++)
        {
            printf("%d ", heap->elements[i]);
        }
        printf("\n");
    }
}

void FreeHeap(Heap heap)
{
    free(heap->elements);
    free(heap);
}

 

다음은 Max Heap의 ADT이다.

typedef struct HeapStruct *Heap;
struct HeapStruct
{
    int capacity;
    int size;
    int *elements;
};

Heap CreateHeap(int heapSize);
void Insert(Heap heap, int value);
int Find(Heap heap, int value);
void DeleteMax(Heap heap);
void printHeap(Heap heap);
void FreeHeap(Heap heap);

 

다음은 Max Heap의 구현체이다.

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

Heap CreateHeap(int heapSize)
{
    Heap heap = (Heap)malloc(sizeof(struct HeapStruct));

    heap->capacity = heapSize;
    heap->size = 0;
    heap->elements = (int *)malloc(sizeof(int) * (heap->capacity));
    heap->elements[0] = 2147483647;

    return heap;
}

void Insert(Heap heap, int value)
{
    int i;
    if (heap->size == heap->capacity)
    {
        printf("Insertion Error: Max Heap is full.\n");
    }
    else if (Find(heap, value))
    {
        printf("%d is already in the heap.\n", value);
    }
    else
    {
        for (i = ++(heap->size); heap->elements[i / 2] < value; i /= 2)
        {
            heap->elements[i] = heap->elements[i / 2];
        }
        heap->elements[i] = value;
        printf("Insert %d\n", value);
    }
}

int Find(Heap heap, int value)
{
    for (int i = 1; i <= heap->size; i++)
    {
        if (heap->elements[i] && heap->elements[i] == value)
            return 1;
    }
    return 0;
}

void DeleteMax(Heap heap)
{
    if (heap->size == 0)
    {
        printf("Deletion Error: Max Heap is empty!\n");
    }
    else
    {
        int i, Child;
        int MaxElement, LastElement;

        MaxElement = heap->elements[1];
        LastElement = heap->elements[(heap->size)--];

        for (i = 1; i * 2 <= heap->size; i = Child)
        {
            Child = i * 2;
            if (Child != heap->size && heap->elements[Child + 1] > heap->elements[Child])
                Child++;

            if (LastElement < heap->elements[Child])
                heap->elements[i] = heap->elements[Child];
            else
                break;
        }
        heap->elements[i] = LastElement;

        printf("Max element(%d) deleted.\n", MaxElement);
    }
}

void printHeap(Heap heap)
{
    if (heap->size == 0)
        printf("Max Heap is empty!\n");
    else
    {
        for (int i = 1; i <= heap->size; i++)
        {
            printf("%d ", heap->elements[i]);
        }
        printf("\n");
    }
}

void FreeHeap(Heap heap)
{
    free(heap->elements);
    free(heap);
}