우선순위 큐란?
우선순위의 개념을 큐(Queue)에 도입한 자료구조이다.
보통 큐는 선입 선출(FIFO) 즉, 먼저 들어간 데이터가 먼저 나오는 차례대로 방식이다.
- 배열을 사용하는 방법
- 연결 리스트를 사용하는 방법
- 히프를 사용하는 방법
히프의 효율은 O(log2n) 으로 다른 방법보다 상당히 빠르다.
| 표현 방법 | 삽 입 | 삭 제 |
| 순서없는 배열 | O(1) | O(n) |
| 순서없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 리스트 | O(n) | O(1) |
| 히프 | O(log2n) | O(log2n) |
히프
히프는 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
■ 최소 히프 : 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
간단히 설명하면, 신입사원이 회사에 들어가면 말단에 있다가 능력을 봐서 승진시키는 것과 같다.
다음과 같이 요소 '8' 을 제일 뒤에 삽입한다.
완전이진트리 성질에 만족시키기위해 4의 right부분에 삽입한다.
부모노드 4와 비교해서 8이 더 크므로 교환한다. 그 위에 할아버지 벌이었던 요소 '7'과 비교해보니 '8'이 더 크다.
또 7과 자리를 바꾼다.
또 그위 부모노드 '9'와 비교해보니 9를 이기진 못한다.
더이상 작업을 중단하고 최종적으로 다음과 같은 트리가 완성된다.
말단이었던 요소 '8'이 능력이 좋다보니 저 자리까지 승진하게 된 것이다.
삭제 연산은 좀 말이 안되지만, 사장이 자리에서 물러나게하고 제일 말단 사원을 사장자리에 올린다.
그러면 회사가 돌아가지 않으니 능력을 다시확인하여 아래 사람과 능력을 비교해서 점점 레벨을 낮춘다.(교환)
앞서 사용한 위 트리에서 최대값을 가진 요소를 삭제하게 되는데 요소'9'를 먼저 삭제하고,
맨아래 요소 '4'를 사장자리(꼭대기)에 올리도록 한다.
그림자료를 따로 첨부하지않고 설명한다.
맨 윗자리에 오른 요소 '4'는 왼쪽 아래 자식인 '8'과 비교해보니 자신의 능력이 형편없는걸 느낀다.
자리를 바꾼다. 요소 '8'이 사장자리에 올라가게되고 원래 '8'자리에 앉게된 '4'는 다시 자식을 보니
'5'와 '7'이 있다. 여기서 중요한건 자식중 더 큰 값과 비교를 하게된다.
그러므로, '7'과 비교해보니 역시나 자신보다 능력이 좋다. 자리를 바꿔준다.
다시 자식을 비교해보니 '3'이 하나 남아서 보니 나보다는 못한다. 다행이다. 이제 더이상
안바꿔도 된다.
실제 원리는 어렵지않으나 코드를 짜려고하니 막막하다.
삭제함수를 코드로 보자면 다음과 같다.
주석을 보면서 코드를 분석하면 알겠지만 주인공인 '말단노드'를 맨 위로 올리고나서 자식 요소와
비교하면서 매번 자리를 바꾸는게 아니라 자식을 계속 승진(레벨업) 시켜주다가
더이상 주인공보다 더 능력이 좋은 요소를 만나지않으면 현재 그 위치에 안착 시키는 방법이다.
#define MAX_ELEMENT 200
typedef struct {
int key;
}element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
}HeapType; //전체 힙 구조체
element delete_max_heap(HeapType *h)
{
int parent, child;
element item, temp; //임시 요소를 담는 구조체 선언
item = h->heap[1]; //힙의 첫번째 즉 삭제할 요소를 item에 담아놓는다.
temp = h->heap[(h->heap_size)--]; //temp에 주인공이 될 '말단 값' 집어넣는다.
parent= 1; //말단이 위치할 자리이다.
child = 2; //말단의 자식 인덱스다.
while( child <= h->heap_size ) //자식 index가 heap의 크기보다 크면 안된다.
{
// 왼쪽자식과 오른쪽자식과 크기를 비교해서 크다면 인덱스를 변경해주는 부분
if( (child < h->heap_size ) && (h->heap[child].key) < h->heap[child+1].key)
child++;
if(temp.key >= h->heap[child].key)
//주인공 '말단'의 값과 비교대상 자식 값과 비교한다.
break; //말단'의 능력(값)이 크면 그대로 멈춘다.
parent = child; //주인공보다 자식값이 크면 현재 위치 parent 에 child를 위치
child = child*2; //그리고 자식위치에는 자식의*2 즉, 자식의 자식인 손자를 위치
}
h->heap[parent] = temp; //현재 주인공을 parent 즉 현재 가르키고있는 위치에 그대로 둔다.
return item; //코드윗줄에서 미리 담았던 값을 리턴한다.
}
참고 책 (그림이 많이 들어가서 이해하기 쉽다. )
|
|||||||||||
'자료구조' 카테고리의 다른 글
| 퀵소트 구현 소스 (6) | 2012.02.18 |
|---|---|
| 더블 링크드 리스트 (0) | 2012.01.16 |
