배열 기반의 힙 , 우선순위 큐 구현 하기

각각의 노드는 유일한 키 값을 가지게 되는데, 노드 중에서 최대값이나 최소값을 빠른시간 내에 찾기 위해서 만든 자료구조가 바로 힙(Heap)이다. 

우선 배열로 트리를 구성하기 위해서 노드에 고유한 번호를  부여한다  그리고 

각 번호가  각 노드의 데이터가  저장될  배열의 인덱스 값이 된다 

  1:A

2:B        3:C

4:D   5:E

구현의 편의를 위해서 인덱스 0의 위치의 배열 요소는 사용하지 않는다 .

배열 기반의 힙을 구성하기 위해서 알아야 할것들 

1. 왼쪽과 오른쪽 자식노드의 인덱스의 값을 얻는 방법 

2. 부모의 인덱스를 얻는 방법 

왼쪽 자식 노드의 인덱스 값 -- 부모노드의 인덱스 값 * 2

오른쪽 자식 노드의 인덱스 값 -- 부모노드의 인덱스 값 * 2+1

부모노드의 인덱스 값-- 자식 노드의 인덱스 값 /2

자식의 노드의 인덱스 값을 얻는 이유는 데이터의 삭제를 위해서 

부모의 노드의 인덱스 값을 얻는 이유는 데이터 추가를 위해서 

여기서 부모노드의 인덱스 값을 구할때 정수 형 나눗셈이다  즉 5를 2로 나누었을때 결과는 2.5 가 아닌 2이다 .

1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

2-1. 루트의 자식노드 두개중과 우선순위가 낮은것과 비교해서 스왑을 안하는 이유는 그렇게 했을 경우 힙의 기본조건이 무너지기 때문이다. 

힙을 구현을 할려면 링크드리스트 ? 배열 ? 어느것이 원칙일까?

답은 배열이다 

왜냐하면  연결리스트를 기반으로 힙을 구현 하면 새로운 노드를  힙의 마지막의 위치에 추가 하는것이 쉽지 않다 .

힙 소스의  * Hinsert --힙에 데이터 삽입  ,* Hdelete --힙에 데이터 삭제  는  우선순위 큐의 enqueue , dequeue 연산 결과와 일치한다   

package Datastructure;

/*GetparentIdx -- 부모 노드의 인덱스 값 반환 

 * GetRchildIdx --  오른쪽 자식노드의 인덱스 값 반환 

 * GetLchildIdx -- 왼쪽 자식노드의 인덱스 값 반환 

 * minHeapify--  루트와 자식노드를 비교 해서 루트와 자식 값 변경 해주는 함수 삭제시 이용한다 

 * isLeaf -- 비교할 자식이 있는가  

 * Hinsert --힙에 데이터 삽입 

 * Hdelete --힙에 데이터 삭제 

 * MinHeap 으로 구현 할것이다

 * root 값이 가장 작다 

 *1.힙 구현 삽입시

힙을 구현 하기위해서는  마지막 위치(마지막 레벨 노드에 오른쪽 위치)에 노드 추가 한후  그리고 마지막위치에 추가한 노드와 그의 부모노드를 계속해서 비교해서 제대로된 위치에 위치 시킵니다.

2. 힙 구현 삭제시 

-1 루트 삭제 

-2 맨 아래 레벨의 오른쪽 노드를  비어져 있는 루트에 옮겨 놓고 옮겨진 루트의 자식노드 두개중에 우선순위가 높은것과 비교해서 올바른 자리를 자리를 찾아간다 .

 

 *

 */

public class Heaparray {

int [] heap;

int heapsize;

//int priority;

int capacity; 

public Heaparray(int size){

heap = new int [size];

heapsize=1;

this.capacity =size;

}

public boolean isempty(){

if(heapsize==0){

return true;

}

else {

return false;

}

}

public boolean isfull(){

if(heapsize ==capacity){

return true;

}else{

return false;

}

}

public void Hinsert(int input){

if(isfull()){

System.out.println("heap overflow error");

}

else {

heap[heapsize]=input;

int current=this.heapsize;// 이게 포인트다 이 부분을 안해주고 heapsize를 이용해서 while문을 돌리면 current=GetparentIdx(current)에서 heapsize를 건드려줘서 소스가 꼬인다

while(heap[GetparentIdx(current)]>heap[current]){//minheap 구현 전제하로  마지막노드랑 부모랑 비교 해서 마지막노드가 부모노드 보다 값이 작으면 바꿔줘야한다 

int tmp = heap[current];

heap[current]=heap[GetparentIdx(current)];

heap[GetparentIdx(current)]=tmp;

current=GetparentIdx(current); // 부모로 따라 올라가게 하기 위한 한줄 

}

this.heapsize++;

}

}

public boolean isLeaf(int idx){//비교할 자식이 있는가?

//마지막  바로윗레벨 과 제일 마지막 레벨에서 부모와 자식은 힙이 성립 하는 이상 비교 할필요가 없으므로 마지막 바로전 레벨에 도착하면 이함수를 끝내준다

if(idx>=(heapsize/2)&& idx<heapsize){// insert 마지막에 heapsize++를 해줘서 < 로 해줌  

//GetparentIdx(idx)>=1&&idx<this.heapsize 자식인가의 조건이 아님 

//heap[idx]>heap[1]&&heap[heapsize-1]>=heap[idx] 이조건은 실패 

System.out.println("비교할자식이 없다");

return false; //

}else{

System.out.println("비교할자식이 있다");

return true; // 

}

}

public void minHeapify(int idx){

if(isLeaf(idx)){// 비교할 자식이 있다면 

if(heap[idx]>heap[GetLchildIdx(idx)]|| heap[idx]>heap[GetRchildIdx(idx)]){

if(heap[GetLchildIdx(idx)] <heap[GetRchildIdx(idx)]){// 왼쪽자식이 작은경우 왼쪽자식이랑 루트랑 바꺼줌

int tmp=heap[idx];

heap[idx]=heap[GetLchildIdx(idx)];

heap[GetLchildIdx(idx)]=tmp;

minHeapify(GetLchildIdx(idx));

}else{// 오른쪽 자식이 작은경우 오른쪽 자식이랑 루트랑 바꺼줌

int tmp=heap[idx];

heap[idx]= heap[GetRchildIdx(idx)];

heap[GetRchildIdx(idx)]=tmp;

minHeapify(GetRchildIdx(idx));

}

}

}

}

public void Hdelete(){

int front=1;

heap[front]=heap[heapsize-1];// insert heapsize++; 때문에

heap[heapsize-1]=0;

heapsize--;

minHeapify(front);// 루트부터 자식들을 비교하는 과정 

}

public int GetparentIdx(int idx){

return idx/2;

}

public int GetLchildIdx(int idx){

return idx*2;

}

public int GetRchildIdx(int idx){

return idx*2+1;

}

public void see(int a[]){

for(int i=0; i<this.heapsize; i++){

System.out.println(a[i]);

}

}

public static void main(String[] args) {

Heaparray h = new Heaparray(7);

h.Hinsert(5);

h.Hinsert(6);

h.Hinsert(3);

h.Hinsert(1);

h.Hinsert(2);

h.Hinsert(4);

//h.see(h.heap);// 일단 insert 부분 성공 

h.Hdelete();

h.Hdelete();

h.see(h.heap);

//h.isLeaf(7);

//System.out.println(h.heapsize);

//System.out.println(h.heap[h.heapsize]);// heapsize를 인서트문에서 올려줘서 outofboundexception 뜬다

// 정렬 이 안되서 맨마지막 노드가 5인데  5보다 커서  즉 인덱스가 루트인덱스 부터 마지막 인덱스까지 인경우  이런식 접근으로 하면안돌거같은데

// 부모가 존재하는지 

}

}

/*test

 * int a[]= new int [2];

a[0]=Integer.MIN_VALUE;

System.out.println(a[0]);*/

                                               1

                                   2                     4

                          6           3          5

이런식으로 나왔습니다  

모든 부모들은 자식보다는 작은 값이라는 전제는 전부 지켜졌습니다. 

하지만  2의 오른쪽 자식 노드 값 3은  1의 오른쪽 자식 노드 보다 작은 값이지만 더 낮은 레벨에 있습니다 . 

이상태여도 힙인 상태인지 의문이 들었는데요 

이 의문에 대한 답은 힙이다  

두번째 의문  2의 왼쪽 자식과 오른쪽 자식의 값이 왠지  바껴야 힙이 될거 같지만  지금 이대로도 힙이 성립 되는것이다 .

위 소스 결과 값 

                      1

                                   2                     4

                          6           3          5

delete 하고 나서 

2

3 4

6 5

delete  하고 나서    

3

5 4

6

http://lemeraldl.tistory.com/admin/entry/post/?id=168

http://www.sanfoundry.com/java-program-implement-binary-heap/

http://www.sanfoundry.com/java-program-implement-min-heap/