[EKOO의 JAVA를 이용한 자료구조:11회] Heap (2)

[EKOO의 JAVA를 이용한 자료구조:11회] Heap (2)

저자:EKOO| 날짜: 2005년 07월 22일

 

Heap을 이용한 Priority Queue ADT

 Heap을 이용하여 Priority Queue를 만들 수 있습니다. 하지만 Priority Queue를 꼭 Heap만을 이용하여 만들수 있다는 것은 아닙니다. 한가지 방법일 뿐이죠. Queue는 자료구조 강좌 6회에서 이미 접해보신 자료구조입니다.

 Priority Queue는 무엇일까요? 본래 Queue는 FIFO(First In First Out)규칙을 따라서 제일 먼저 Queue에 넣은것이 가장 먼저 나오게 됩니다. 예를 들어 윈도우의 메시지들도 Message Queue라는 곳에 들어갔다가 하나씩 꺼내서 나오게 되는 구조로 되어있죠. 하지만 Priority Queue는 먼저들어갔다고 무조건 먼저 나오지 않습니다. 기본적으로 FIFO규칙을 따르지만 원소마다 우선순위가 매겨져 있어서 나중에 Priority Queue에 들어갔더라도 우선순위가 높다면 먼저 들어온 원소보다도 일찍 처리될 수 있는것입니다.

 원소의 크기가 클수록 우선순위가 높다고 가정하고 그것을 기준으로 하는 Priority Queue를 Heap을 이용해서 작성할 수 있습니다.

Priority Queue의 추가

 이제는 Heap을 이용하여 Priority Queue를 짜보도록 하겠습니다. Heap의 규칙중에 부모 Node의 원소는 자식 Node의 원소보다 반드시 커야만 하죠? 밑의 그림을 예로 들어서 하나하나 설명하도록 하겠습니다.

[그림 2] Heap을 이용한 Priority Queue
 위의 형태로 이미 Queue가 구현이 되어 있다고 가정해 보겠습니다. Queue나 Stack같은 자료구조는 추가, 삭제의 작업은 필수적이므로 추가하는 과정을 살펴보도록 하겠습니다. 한가지 유의하실 점은 Heap의 3가지 조건을 반드시 만족해 가면서 작업을 해야만 한다는 것 입니다.

[그림 3] Priority Queue의 추가과정
 5개의 과정을 거쳐서 Priority Queue의 추가과정이 완성되었습니다. (2)번의 과정에서는 일단 Complete Binary Tree의 조건을 만족시킵니다. 하지만 Heap의 조건을 만족시키지는 못하죠. 그래서 부모 Node의 원소와 비교를 통해서 두개의 원소를 Swap(3)하게 됩니다. (4)번의 과정에서는 부모 Node의 원소가 자신의 원소보다 크기 때문에 Heap의 조건을 만족시켜서 더이상 Swap할 필요가 없기 때문에 Add과정이 완료가 됩니다.

public void add(int element){ 새로운 Node 생성 새로운 Node를 Full Binary Tree의 조건에 만족하도록 Heap에 삽입 현재 가리키고 있는 노드가 Heap에 추가한 Node가 되도록 설정 while(1) { 현재 가리키고 있는 Node와 그 Node의 부모 Node의 element를 비교하여 Swap 할지를 결정 if( swap을 했다면 ) { 현재 가리키고 있는 Node역시 swap을 해준다. ex) point = point.GetParentNode(); } else { break; } }}