자료구조 힙(heap)

우선순위 큐

힙은 쌓아 올린 더미라고 생각할 수 있고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징한다. 힙을 설명하기 위해 우선 우선순 순위 큐를 알아야 하는데 큐는 배웠듯이 먼저 들어간 데이터가 먼저 삭제되는 자료구조이다. 대기열리스트에서 항상 우선순위가 높은 것을 먼저처리하는 것이고 이것은 항상 꼭대기에 있다고 생각하면 됩니다.

우선순위 큐 역시 큐여서 들어가는 위치인 rear과 나오는 위치인 front가 정해져 있다. 

우선순위 큐

우선순위 큐의 작동방식은

1. 삭제 명령이 실행되면 데이터 중 가장 작은 값 혹은 가장 큰 값이 삭제된다.
2. 나머지 데이터들은 어떤 순서로 저장이 되든 상관은 없다.

힙

힙의 정의

힙은 피라미드 모양으로 쌓아 올린 더미와 유사한 모양이다. 항상 가장 위에 있는 것을 우선 꺼내는 구조이다.

부모-자식노드 사이에서 부분적으로 정렬된 완전이진트리로 부모노드는 자식노드보다 우선순위가 높다. 쉽게 힙은 우선순위 큐의 한 종류이고 트리로 구현한 게 바로 힙이다. 부모와 자식 노드 사이에 일정한 대소관계를 유지해야 하는 조건이 추가가 된 것이다.

 

힙의 추상 자료형

힙 객체의 정의 : 부분적으로 정렬된 완전 이진트리로 부모 노드는 자식노드 보다 우선순위가 높다.
연산
1. insert(element) : := 힙에 데이터 삽입
2. delete( ) : := 힙(루트)에서 데이터 삭제
3. peek( ) : := 힙(루트)에서 데이터 읽어오기
4. isEmpty( ) : := 힙이 비어있는지 확인
5. size( ) : := 힙에 저장하는 데이터 개수 확인

힙의 종류

힙은 두 가지 루트의 값이 가장 작은 순서인 것을 최소힙, 반대인 것이 최대 힙이다.

그래서 힙이 아닌 경우를 보려면 최소힙 또는 최대힙인지 확인하고 완전 이진트리가 맞는지 확인해야 한다.

완전이진트리가 아니다.

힙의 삭제와 삽입연산

힙은 배열을 이용해서 힙을 구현하면 기역장소 낭비가 없다. 연결 리스트보다 실행속도면에서 효율적이고(포인터가 아니라 인덱스 값을 찾아가니까 빠르다), 기억장소 측면에서도 장점을 갖는다.

배열은 인덱스인 위치를 알 수 있다. 그래서 부모노드와 자식노드의 위치를 알 수 있는데 왼쪽 자식노드의 위치를 i라고 하면 오른쪽 자식노드는 i+1이고 그 두 노드의 부모는 i/2이다.

 

힙의 루트 노드삭제

힙에서의 삭제는 루트에서 삭제를 의미한다.(큐를 생각하자.)

위그림에서 예를 들어보자. 루트인 1이 삭제가 되고 가장 뒤에 있는 9가 루트로 먼저 올라온다. 그리고 자식노드인 2와 3을 비교해서 본인보다 작고 자식노드 2개 중 작은 2를 올리고 2자리에 9가 간다. 역시 반복해서 4를 9자리로 그리고 8을 9자리로 바꾸면 완전이진트리가 된다.

 

typedef struct heap {
int heap [MAX_SIZE];
int size;
} heap;
int min heapDelete(heap *h){
int parent, child;
int data, temp;

data=h→heap [1]; //루트값
temp=h→heap[(h→size)--];
praent=1;
child=2;

while(child <=h → size) {
if((child < h → size)&&(h→heap [child]>h→heap [child+1)){  //여기선 새로운 부모를 가지고 자식노드 위치를 찾는 것이다.

child++;}
if(temp <= h→  heap [child])  
break;}
h→heap [parent] = h→heap [child];
parent = child;
child *=2;
}
h→heap [parent]=temp;
return data;
}

힙에서 노드 삽입 

void min_heapInsert(heap *h,int data){
int i;
i=++(h→size);
while((i !=1)&&(data<h→heap[1/2])){  //부모노드와 비교해서 크다면(혹은 작다면) 부모노드로 올라가는 것을 반복 그리고 부모노드로 올라갈 때 오른쪽노드라면 홀수이다. 하지만 부모노드가 실수가 아니고 정수임으로 상관이 없다.//
h→heap [i]=h→heap [i/2];
i /=2;
}
h→heap [i]=data;
}

위에서 data<h→heap[1/2] 새롭게 넣는 i가  (i/2) 위치에 있는 부모노드와 크기를 비교해 작다(크다) 면 h→heap [i]=h→heap [i/2];를 통해 부모와 자식의 값을 바꾼다 그리고 i는 인덱스위치를 말하므로 반복을 위해 i의 값을 위치를 바꾼 자리로 이동시킨다.