9-2. 힢 노드의 삭제 및 삽입

03. 힢 노드의 삭제 및 삽입

힢 구현을 위한 자료구조

배열을 이용한 힙의 구현 : 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음

→ 연걸 리스트보다 실행 속도 면에서 효율적임

→ 기억장소 측면에서도 장점을 가짐

 

배열을 이용한 힢의 구현

힢의 노드 삭제

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->heap_size){
	if((child < h->heap_size)&&(h->heap[child] > h->heap[child+1]))
		child++;
	if(temp <= h->heap[child])
		break;
	h->heap[parent] = h->heap[child];
	parent = child;
	child *= 2;
	}
	h -> heap[parent] = temp;
	return item;					}

 

힢의 노드 삽입

void insertHeap(HeapType *h,intitem){
	inti; 
    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; 			}