[자료구조][C] 힙의 개념과 구현

Heap

Heap(힙)이란?

부모의 값이 자식의 값보다 항상 작은(또는 큰) 완전이진트리

부모? 자식? 완전이진트리?

Heap을 알기 위해서는 Tree부터 알아야한다.

 

Tree(트리)란?

트리의 이미지

출처: https://www.tutorialspoint.com/data_structures_algorithms/images/binary_tree.jpg

 

간단히 알고 넘어가자:

Root(루트) 트리의 가장 윗부분

Node(노드, 요소) 트리에서 데이터를 담는 것

Edge(에지, 간선) 노드와 노드를 연결 하는 것

Level(레벨, 층): 루트노드로부터의 거리

 

노드의 상하 관계: 부모(parent) - 자식(child) 관계

같은 부모노드 밑에 있는 노드: 형제(sibling)

 

완전이진트리(Complete Binary Tree)

완전이진 상태인 트리

완전: 왼쪽부터 자식이 있는 부모의 모양

이진: 부모가 가질 수 있는 노드는 최대 2개

 

위 그림은 완전이진트리이다.

 

트리의 구현

배열로 구현한다

 

완전이진트리의 자식노드가 추가되는 순서대로 배열에 입력한다.

 

 

빨간색 숫자는 완전이진트리에 노드가 추가되는 순서이다

파란색 숫자는 임의의 완전이진트리를 배열로 구현한 모습이다.

 

트리의 요소 tree[i]에서 다음과 같은 인덱스 관계가 성립한다.

 

1. 부모는 tree[(i-1) / 2]
2. 왼쪽 자식은 tree[i * 2 + 1]
3. 오른쪽 자식은 tree[i * 2 + 2]

예시:

tree[3]의 부모는 tree[1]

tree[1]의 왼쪽 자식은 tree[3]

tree[1]의 오른쪽 자식은 tree[4]

 

만약 배열의 1번 인덱스부터 채운다면 관계는 더 간단해진다

 

1. 부모는 tree[i / 2]
2. 왼쪽 자식은 tree[i * 2]
3. 오른쪽 자식은 tree[i * 2 + 1]

 

힙 정렬

가장 작은 값(최소 힙, 큰 값이면 최대힙)이 루트에 위치하는 특징을 이용하는 정렬 알고리즘

 

아래는 최소힙이라고 가정한 과정이다. 최대힙일 때는 알잘딱하게 바꾸자

삽입

1. 마지막 리프 노드에 데이터를 삽입한다.
2. 부모 노드와 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap한다.
3. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.
   즉, 2번 조건을 만족하거나, 루트노드가 되면 반복을 종료한다.

삭제

1. 루트 노드의 값(최소값)을 저장한다.
2. 가장 마지막 노드의 값과 루트 노드의 값을 swap 한다.
3. 현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap한다.
   두 자식을 비교하여 더 작은 값을 가지는 노드와 swap한다.
4. 위치를 찾을 때 까지 3번 과정을 반복한다.

시간복잡도

힙은 트리의 높이만큼 비교한다. 노드 N개가 있는 트리의 높이는 logN이므로

힙 정렬의 시간복잡도는 O(logN)이다.

 

구현 C

#include <stdio.h>
#define MAX_NUM 100001

int heap[MAX_NUM], size = 1, target, next, temp_node;

int pop()
{
    if (size == 1)
        return 0;

    else
    {
        int res = heap[1];      // 가장 작은 값 반환
        heap[1] = heap[--size]; // 마지막 노드 값 루트 노드로

        for (target = 1; target * 2 < size;)
        {
            if (size > target * 2 + 1)
                // 자식노드 2개 중 작은 값 선택
                next = heap[target * 2] < heap[target * 2 + 1] ? target * 2 : target * 2 + 1;
            else
                next = target * 2; // 자식노드 1개 뿐일 때

            if (heap[target] > heap[next]) // 부모노드가 자식노드보다 크면 swap
            {
                temp_node = heap[target];
                heap[target] = heap[next];
                heap[next] = temp_node;
                target = next;
            }
            else
                break;
        }
        // 최소 힙 만족하게 정리 후 값 반환
        return res;
    }
}

void push(int data)
{
    heap[size++] = data;
    for (target = size - 1; heap[target] < heap[target / 2]; target /= 2)
    {
        temp_node = heap[target];
        heap[target] = heap[target / 2];
        heap[target / 2] = temp_node;
    }
}
int main()
{
    int num_cases, input;
    scanf("%d", &num_cases);

    while (num_cases--)
    {
        scanf("%d", &input);

        if (input == 0)
            printf("%d\n", pop());
        else
            push(input);
    }
    return 0;
}