1. 우선 순위 큐
1.1. 큐와 우선순위 큐
•
큐
◦
먼저 들어간 데이터가 먼저 삭제되는 자료구조
•
우선 순위큐
◦
대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조
1.2. 우선순위 큐의 배열 구현
•
데이터 삭제시 우선순위 고려
•
삽입 시에는 우선순위를 고려하지 않고 삽입
◦
삭제 외 나머지 데이터들은 어떤 순서로 저장되든 문제되지 않음
2. 힙
2.1. 정의
•
피라미드 모양을 쌓아 올린 더미
•
무언가를 쌓아놓은 더미, 항상 가장 위에 있는 것을 우선 꺼내는 구조
•
부모-자식 노드 사이에서(부분적으로) 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음
2.1. 힙의 종류
•
최소 힢: 루트가 전체 노드중에서 최소값인 힢 (부모노드 < 자식 노드)
◦
특징
▪
트리의 모든 노드가 자식 노드보다 작은 값을 가짐
▪
트리의 레벨에 따라 데이터가 순서를 갖지는 않음
▪
탐색 트리처럼 왼쪽노드와 오른쪽 노드사이에 크기 제한이 없음
▪
루트가 가장 작은 값을 갖고 부모는 자식 보다 작은 값을 가짐
◦
예
•
최대 힙: 루트가 최대 값을 가짐
◦
예
2.2. 힙의 추상자료형
•
힙 객체의 정의
◦
부분적으로 정렬된 완전 이진트리
◦
부모노드는 자식 노드보다 우선순위가 높다
•
연산
◦
insert(element)
◦
remove()
◦
peek()
◦
isEmpty()
◦
size()
2.3. 힙이 아닌 경우
•
완전 이진 트리가 아닌 경우
•
(최소 힙) 부모 노드가 자식노드보다 큰 경우
3. 힙 노드의 삭제 및 삽입
3.1. 힙 구현을 위한 자료구조
•
배열을 이용한 힙의 구현
◦
완전 이진트리이므로 배열로 구현해도 기억장소 낭비가 없음
◦
연결 리스트보다 실행 속도 면에서 효율적
◦
기억장소 측면에서도 장점을 가짐
3.2. 힙의 노드 삭제
// 루트노드의 인덱스는 1로 시작함 (*를 사용하기위함)
typedef struct {
int heap(MAX_Data];
int heap_size;
} HeapType;
int deleteHeap(HeapType *h){
int parent, child;
int item, temp;
item = h->heap[1]; // 첫번째 인덱스 값
temp = h->heap[(h->heap_size)--]; // 마지막 값
parent = 1;
child = 2;
while(child <= h->heapsize) {
if((child < h->heapsize) && (h->heap[child] > heap[child+1]))
child++;
if(temp <= h->heap[child])
break;
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
}
C
복사
3.3 힙의 노드 삽입
void insertHeap(HeapType *h, int item){
int i;
i = ++(h->heap_size);
while((i != 1) && (item < h->heap[i/2])) {
h->heap[i] = h->heap[i/2];
i /= 2;
}
h->heap[i] = item;
}
C
복사
•
마지막 노드에 삽입
•
7과 12를 교환
•
7과 10을 교환후 종료
