[DS] 힙(Heap)이란?

힙(Heap)이란?

완전이진트리(complete binary tree)이면서 최대트리(max-tree)를 만족하는 이진트리(binary tree)입니다.

힙(heap)은 저장된 원소 중 가장 값(key)이 큰 원소를 제공하는 데이터 구조입니다.

 

 

완전이진트리(complete binary tree)란?

https://yyyeji.tistory.com/370

[DS] 이진트리(Binary Tree)란?

n개의 노드(node)가 level 순서로 모두 채워진 이진트리(binary tree)입니다.

노드(node)가 위에서 아래로 왼쪽부터 오른쪽으로 잘 채워져 있으면 됩니다.

 

 

 

최대트리(max-tree)란?

상위 노드(parent node)의 값(key)이 하위 노드(child node)의 값(key)보다 큰 트리(tree)를 말합니다.

즉, 어떤 node의 값(key)은 모든 하위 노드들(descendents)의 값(key)보다 항상 큰 트리(tree)입니다.

 

 

 

 

Heap의 표현

---

아래와 같은 힙(heap)이 있다고 가정해보겠습니다.

0	1	2	3	4	5	6	7	8	9
	100	80	90	70	50	60	40	30	20

저는 root node를 1로 가정하고 설명하겠습니다.

i번째 노드(node)를 기준으로 left child, right child, parent 원소를 어떻게 접근할지 살펴봅시다.

(index를 기준으로 생각하면 쉽습니다.)

 

left child node

2 * i

ex) root를 기준으로 2를 곱해주면 됩니다.

1*2 = 2 (2번째 node - root의 left child node)

 

right child node

2 * i + 1

ex) root를 기준으로 2를 곱해주면 left child로 이동되고, +1을 해주면 됩니다.

i*2+1 (3번재 node - root의 right child node)

 

parent node

i / 2

ex) child node에서 나누기 2를 해주면 그 결과의 몫이 parent node가 됩니다.

2/2 = 1(root node) or 3/2 = 1(root node)

 

 

 

Heap을 구현하기 위한 ADT 정의

---

class element {
public: 
    string name;
    double score;
    void set_data(string s, double d);
};

원소의 값을 위한 클래스를 하나 정의해 줍니다.

 

class heap {
    element h[HSIZE];
    int csize;
public:
    heap();
    int h_size();
    void insert_heap(element e);
    element delete_heap();
    bool heap_full();
    bool heap_empty();
};

h_size - 힙(heap)을 생성한 초기 상태

insert_heap - heap에 원소 한 개 추가

delete_heap - heap의 top 원소 하나 return

heap_full - 현재 head이 full인지에 대한 상태 확인

heap_empty - 현재 heap이 empty인지에 대한 상태 확인

 

 

 

함수 구현

---

void element::set_data(string s, double d) {
    name = s;
    score = d;
}

element class의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

heap::heap() {
    csize = 0;
}

heap class의 생성자(constructor)에서는 csize(heap의 size)를 0으로 초기화시켜 줍니다.

 

 

int heap::h_size() {
    return csize;
}

h_size는 현재 heap의 크기(size)를 return해주는 함수입니다.

heap의 현재 size를 return 해줍니다.

 

 

void heap::insert_heap(element e) {
    int k;
    csize++;
    k = csize;

    while((k!=1) && (e.score > h[k/2].score)) {
        h[k] = h[k/2];
        k/=2;
    }
    h[k] = e;
}

insert_heap은 heap에 원소를 추가하는 함수입니다.

 

csize++;

heap에 원소를 추가하기 때문에 heap의 size를 증가시킵니다.

 

while문은 새로운 원소가 추가될 index(위치)를 찾기 위한 반복문입니다.

while((k!=1) && (e.score>h[k/2].score))

현재 k의 값이 root가 아니고,

추가되려고 하는 score 값이랑 k가 가르키고 있는 노드(node)의 상위 노드(parent node)와 비교를 해서

상위 노드(parent node)보다 값이 크면 while문을 실행시킵니다.

k!=1 -> root X, key of child node > key of parent node

 

h[k] = h[k/2];

현재 넣으려고 하는 score의 값이 상위 노드(parent node)보다 크면 넣으려고 하는 값을 상위 노드(parent node)로 만들어야 됩니다.

이 코드는 상위 노드(parent node)의 값(key)을 하위 노드(child node)로 옮기는 코드입니다.

 

k/=2;

k가 가르키는 곳을 상위 노드(parent node)로 옮깁니다.

 

h[k] = e;

while문이 종료되면 현재 k가 가르키고 있는 heap의 위치에 원소를 추가합니다.

 

 

element heap::delete_heap() {
    element t;
    element tmp;
    int parent, child;

    t = h[1];
    tmp = h[csize];
    csize--;
    parent = 1;
    child = 2;

    while(child <= csize) {
        if((child < csize) && h[child].score < h[child+1].score) 
            child++;
        if(tmp.score >= h[child].score)
            break;
        
        h[parent] = h[child];
        parent = child;
        child *= 2;
    }
    h[parent] = tmp;

    return t;
}

delete_heap은 원소 한 개를 제거하는 함수입니다.

 

t = h[1];

t는 heap의 root를 가르킵니다.

 

tmp = h[cisze];

tmp는 haep의 가장 마지막 원소를 가르킵니다.

 

csize--;

heap 원소를 하나 제거하기 때문에 csize를 하나 감소시킵니다.

 

parent = 1;

parent는 heap의 root index이고,

 

child = 2;

child는 heap root의 left child node의 index입니다.

 

while(child<=csize)

child node가 있는지 확인하는 조건입니다.

 

if((child<csize) && h[child].score < h[child+1].score) child++;

right child가 존재하고, left child보다 right child의 값이 크면 child의 index를 하나 증가시킵니다.

 

if(tmp.score >= h[child].score) break;

tmp의 값과 현재 child의 값을 비교해서 tmp의 값이 크면 while문을 종료합니다.

 

h[parent] = h[child];

child 값을 parent로 옮깁니다.

 

parent = child;

parent의 index를 child index로 바꿔주고,

 

child *= 2;

child의 index는 left child의 index로 바뀝니다.

 

h[parent] = tmp;

heap parent 위치에 tmp 원소를 넣어줍니다.

 

return t;

처음에 저장해 뒀던 root의 값을 return 합니다.

 

 

 

bool heap::heap_full() {
    if(csize>=HSIZE-1) 
        return true;
    else 
        return false;
}

heap_full은 heap가 꽉 찬 상태인지 확인하는 함수입니다.

heap의 size(크기)인 csize가 HSIZE(100)-1(index 0은 사용 X)보다 크면 true를 return하게 됩니다.

 

 

 

bool heap::heap_empty() {
    if(csize == 0) 
        return true;
    else 
        return false;
}

heap_empty는 heap이 빈 상태인지 확인하는 함수입니다.

heap의 size(크기)인 csize가 0이면 heap이 빈 상태라는 의미이기 때문에 true를 return합니다.

 

 

main 함수 구현

---

int main() {
    heap h;
    element tmp;

    tmp.set_data("A", 99);
    h.insert_heap(tmp);
    tmp.set_data("B", 11);
    h.insert_heap(tmp);
    tmp.set_data("C", 55);
    h.insert_heap(tmp);
    tmp.set_data("D", 77);
    h.insert_heap(tmp);
    tmp.set_data("F", 66);
    h.insert_heap(tmp);
    tmp.set_data("G", 100);
    h.insert_heap(tmp);

    while(h.h_size() > 0) {
        tmp = h.delete_heap();
        cout << tmp.name << ":" << tmp.score << "\n";
    }

    return 0;
}

원소를 하나씩 heap에 넣어줍니다.

그리고 하나씩 출력해보면 점수가 높은 순으로 출력되는 것을 확인할 수 있습니다.

 

 

 

◡̈