[펌_java를 이용한 자료구조] 힙(Heap)

LONG

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; } } }

 

 

ARTICLE 참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며...

 안녕하세요. 이번엔 Heap이라는 자료구조에 대해서 배워보도록 하겠습니다. Heap은 Binary Tree의 일종으로 정렬에서 많이 쓰이는 자료구조 입니다.

 강좌를 시작하기전에 한가지 짚고 넘어가 보도록 하겠습니다. 이미 지난 8회에서 Tree를 다룬적이 있었습니다. 왜 Heap은 Tree에서 다루지 않고 따로 다루는 것일까요? Heap은 물론 Tree개념을 사용하지만 실제로 구현이 Array로 되기 때문입니다. 게다가 막강한 성능의 정렬알고리즘을 사용할 수 있기 때문에 따로 둔것이죠. 이제 Heap의 바다로 한번 뛰어들어 보도록 하겠습니다.

Heap?

 Heap이란 무엇일까요? Tree개념을 이용한 또하나의 자료구조라고 할 수 있습니다. 슬쩍 본다면 Binary Search Tree와 다른점을 찾지 못할지도 모르지만, 그것과는 다른 또다른 규칙들이 존재합니다. 그 규칙들에 대해서는 밑에서 또 다루니 생략하도록 하겠습니다.

 Heap을 이용한 Heap Sort라는 정렬 알고리즘이 있습니다. 이 정렬 알고리즘은 여타 다른 정렬 알고리즘에 비하여 굉장히 빠른 정렬 속도를 자랑합니다. 필자가 처음 Heap Sort를 접해보았을때 빠른 정렬속도를 보고도 믿지 못하여, 아는 선배님께 물어보니 "휙~" 정렬해 버린다고 Heap Sort라고도 한다는군요.

Heap's Rules

 바로 위에서도 말씀드렸듯이 Heap의 규칙에는 무엇들이 있을까요? 단 세가지 규칙만을 따릅니다.

1. Complete Binary Tree  2. 부모 Node에 있는 원소는 자식 Node의 원소보다 반드시 커야만 한다.  3. 가장 깊은 Level의 Node는 반드시 왼쪽에서부터 빈틈없이 오른쪽으로 채워져야 한다.

[그림 1] 여러가지 Binary Tree들
 위 그림1의 (1), (2), (3)중에 어느것이 Heap의 조건을 만족할까요? 한번 맞춰 보시기 바랍니다.

 정답은 (3)번입니다. (1)번은 Heap의 위의 룰중에 3번째 규칙을 어겼습니다. (2)번은 부모 Node의 원소가 자식 Node의 원소보다 작으므로 2번째 룰을 어깁니다. (3)번이 Heap의 모든 조건을 갖춘 Tree의 형태이죠.

 자료의 양이 많든 적든, 위에서 말씀드린 3가지의 규칙만 지켜주신다면 그 자료구조는 Heap이라고 할 수 있습니다.