[자료구조]heap

[들어가기 전]

스택 : FILO 선입 막출

큐 : FIFO 선입 선출

우선순위 큐 : 우선순위가 높은 순서대로 선택

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 힙으로 구현했을 때가 가장 효율적이다.

 

완전 이진트리란?

1.     마지막 레벨을 제외한 모든 레벨 이 완전히 채워져 있다.

2.     마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 외쪽부터 오른쪽으로 채워져야 한다.

-완전 이진 트리인 경우

https://jomuljomul.tistory.com/entry/%EC%99%84%EC%A0%84%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%ACComplete-Binary-Tree%EB%9E%80

-완전 이진 트리가 아닌 경우

 

-힙 구조란?

ü  완전 이진 트리의 일종으로 우선순위 큐로 구현이 가능한 자료구조이다.

ü  여러 값들 중 최댓값이나 최솟값을 빠르게 찾아내는 데 용이한 자료구조이다.

ü  힙은 부모 노드의 값이 자식 노드의 값보다 항상 큰(작은) 이진 트리이다.

ü  힙 트리는 중복된 값을 허용한다.(이진 탐색 트리는 중복된 값을 허용하지 않는다.

 

-힙(heap)의 종류

최대힙: max heap

부모 노드 값 >= 자식 노드 값

 

최소힙: min heap

부모 노드 값<= 자식 노드 값

 

 

 

<C언어로 힙(heap)구조 만들기>

 

*힙(heap)의 구현

ü  구현을 쉽게 하기 위해 첫 번째 인덱스 0은 사용되지 않는다.

ü  힙은 표준적으로 배열로 저장된다.

ü  힙에서 부모 노드와 자식 노드의 관계

-왼쪽 자식 인덱스 = 부모의 인덱스*2

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

-부모의 인덱스 = 자식의 인덱스/2

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

#define MAX_ELEMENT 200 // 힙 안에 저장된 요소의 개수 

//힙의 구현 
typedef struct{
	int key;
}element;

typedef struct{
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

HeapType heap1;

 

 

*힙(heap)의 삽입

1.힙에 새로운 요소가 들어오면 새로운 노드를 힙 마지막 노드에 삽입한다.

2.부모 노드와 새로운 노드를 교환해 힙의 성질을 만족시킨다.

최대힙(max heap) 삽입 과정

//최대힙의 삽입 
void insert_max_heap(HeapType *h, element item){
	int i;
	i=++(h->heap_size); //힙 크기 하나 증가 
	
	while((i!=1)&&(item.key > h->heap[i/2].key)){ // 부모노드 보다 삽입할 노드 값이 더 크다면 
		h->heap[i] = h->heap[i/2]; //부모 노드를 i번째 노드로
		i/=2; 
	}
	h->heap[i] = item; 
}

*힙(heap)의 삭제

1.최대 힙에서 최댓값은 루트 노드이다. 고로 루트 노드가 삭제된다.

2.삭제된 루트 노드에서 힙의 마지막 노드를 가지고 온다.

3.힙을 재구성한다.

최대힙(max heap)에서 최댓값 삭제 과정

//힙의 삭제
element delete_max_heap(HeapType *h){
	int parent, child;
	element item, temp;
	
	item = h->heap[1]; //루트 노드 값 
	temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp변수에 할당하고 힙 크기 -1 
	parent = 1;
	child = 2;
	
	while(child <= h->heap_size){
		//현재 노드의 자식 노드 중 가장 큰 걸 찾는다. 
		if((child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key))
			child++;	
		
		//temp값이 자식 노드 보다 클 경우 힙 정렬 완료 됌 
		if(temp.key >= h->heap[child].key)
			break;
			
		//부모 노드에 자식 노드 값을 삽입 
		h->heap[parent]=h->heap[child];
		//한 레벨 아래로 이동 
		parent = child;
		child *=2;
	}
		//마지막 노드를 재구성한 위치에 삽입 
		h->heap[parent] = temp;
		//루트 노드 값(최댓값) 반환	
		return item;
	
}

 

 

<힙 구현, 삽입, 삭제 C언어 코드>

#include<stdio.h>
#define MAX_ELEMENT 200 // 힙 안에 저장된 요소의 개수 

//힙의 구현 
typedef struct{
	int key;
}element;

typedef struct{
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

HeapType heap1;

//최대힙의 삽입 
void insert_max_heap(HeapType *h, element item){
	int i;
	i=++(h->heap_size); //힙 크기 하나 증가 
	
	while((i!=1)&&(item.key > h->heap[i/2].key)){ // 부모노드 보다 삽입할 노드 값이 더 크다면 
		h->heap[i] = h->heap[i/2]; //부모 노드를 i번째 노드로
		i/=2; 
	}
	h->heap[i] = item; 
} 

//힙의 삭제
element delete_max_heap(HeapType *h){
	int parent, child;
	element item, temp;
	
	item = h->heap[1]; //루트 노드 값 
	temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp변수에 할당하고 힙 크기 -1 
	parent = 1;
	child = 2;
	
	while(child <= h->heap_size){
		//현재 노드의 자식 노드 중 가장 큰 걸 찾는다. 
		if((child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key))
			child++;	
		
		//temp값이 자식 노드 보다 클 경우 힙 정렬 완료 됌 
		if(temp.key >= h->heap[child].key)
			break;
			
		//부모 노드에 자식 노드 값을 삽입 
		h->heap[parent]=h->heap[child];
		//한 레벨 아래로 이동 
		parent = child;
		child *=2;
	}
		//마지막 노드를 재구성한 위치에 삽입 
		h->heap[parent] = temp;
		//루트 노드 값(최댓값) 반환	
		return item;
	
}

int main(void){
	return 0;
}

 

 

출처,참고 :

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html  

 

https://lsoovmee-rhino.tistory.com/48

[자료구조 C 언어] C 프로그래밍 자료구조 - 13 : 힙 트리 (Heap Tree)와 우선 순위 큐 (Priority Queue)

https://jomuljomul.tistory.com/entry/%EC%99%84%EC%A0%84%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%ACComplete-Binary-Tree%EB%9E%80