Heap

Heap은 Data가 마구 모여져있는것인데, 그 중 특징을 가지게 한것이 Max Heap과 Min Heap이다.

 

Maxtree란, 각 node가 자신의 child보다 크거나 같은것. (child가 하나든, 두개든)

 

Max Heap: 

완전 이진트리이면서 maxtree인것.

max heap 예시.

complete binary tree가 아님

 

Min heap : parent가 children보다 작거나 같은것.

 

min heap 예시

max heap은 root가 최댓값. 

min heap은 root가 최솟값.

 

Priority Queue:

내가 어떤 값을 매기는데, 그 중 가장 큰 값을 매긴 애를 찾아낼 수 있는 구조. 

maxheap을 한번 만들면, 맨 위에 최대값이 있고, pop했을 경우 다음 최대값이 root가 되게 설정함.

Complete binarytree덕분에 log(n) 의 시간복잡도로 데이터를 넣고 뺄 수 있다.

 

 

 

다음과 같은 tree에 21을 6번 node에 추가하게되면 parent인 2와 비교해 자리를 바꾸고, 다시 20과 비교해 자리를 바꾼다.

 

tree 의 height가 많아질수록, height만큼만 비교하면 되는 (log(n)의 시간복잡도) 특성이 장점이다.

 

 

-Heap Insertion

 

void push(element item, int *n)
{
int i;
if (HEAP_FULL(*n)) {
fprintf(stderr, "The heap is full. ");
exit(EXIT_FAILURE); //heap이 full인지 체크
}
i = ++(*n);
while ((i != 1) && (item.key > heap[i/2].key)) {
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
}

push라는 함수이다.

element e;
e.key=14;
no=5;
push(e, &no);

 다음과같은 코드를 실행할 때 사용된다.

 

data를 추가하면 n값이 바뀌기 때문에 pointer로 증가해준다. i = ++(*n);

 

i!=1일때까지 (root에 도달할때까지) (while문) 

 

item.key > heap[i/2].key (parent의 key 값이 더 작으면)

heap[i]를 올리고 parent 값을 끌어내린다.

 

-Heap deletion

여기서 20을 제거한다고 생각하면, 다시 형태를 유지해야한다. 어떻게 구현해야할까?

 

[5]번자리를 지워야하니까, 우선 5번 node값을 root로 올린다. 새로 설정된 root값을 children과 비교하며 자신보다 큰 children을 올려주는 개념이다.

element pop(int *n)
{
int parent, child;
element item, temp;
if (HEAP_EMPTY(*n)) {
fprintf(stderr, "The heap is empty");
exit(EXIT_FAILURE);
}
item = heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while (child <= *n) {
if((child<*n)&&
(heap[child].key<heap[child+1].key))
child++;
if (temp.key >= heap[child].key) break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}

 

Heap이 비었는지 우선 확인을 하고

 

item에 root값을 저장하고

temp에 heap의 마지막값을 저장하고, 

*n--를 해준다.

 

while (child <= *n)

-child가 존재하는 동안

 

if((child<*n)&&
(heap[child].key<heap[child+1].key))

-leftchild와 rightchild가 모두 존재하고 left child가 reightchild보다 작으면 child를 1 증가한다.

즉 child라는 애들 children중 큰 애의index.

 

if (temp.key >= heap[child].key) break;

-child보다 temp값이 더 크면 parent자리에 temp가 들어가면 된다.

그렇지 않으면

 

parent는 기존child에 있던 값이 되고 child*2로 그 다음 level을 탐색한다.