[자료구조] 힙

우선순위 큐

• 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조
• 우선순위 큐: 대기 리스트에서 우선순위 높은 사람이 먼저 서비스를 받는 구조
• 데이터 삭제(Delete_q())와 삽입(Add_q(3)): Delete_q()에 의해 큐의 front에 있던 ‘1’이 삭제되면서, 나머지 데이터 중에서 가장 작은 값인 ‘2’가 다음 삭제 위치 즉, front가 가리키는 위치로 이동됨
• 우선순위 큐의 작동 방식
  • 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값)이 삭제된다.
  • 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다.

힙 추상 자료형

• 힙
  • 피라미드 모양으로 쌓아 올린 더미
  • 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조
  • 부모-자식 노드 사이에서(부분적으로) 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높음
• 연산
  • insert(element) ::= 힙에 데이터 삽입
  • delete() ::= 힙(루트)에서 데이터 삭제
  • peek() ::= 힙(루트)에서 데이터 읽어오기
  • isEmpty() ::= 힙이 비었는지 확인
  • size() ::= 힙에 저장한 데이터 개수 확인

힙의 종류

• 최소 힙: 루트가 전체 노드 중에서 최소값인 힙
  • 트리의 모든 노드가 자식 노드보다 작은 값을 가짐
  • 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
  • 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
  • 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐
• 최대 힙: 루트가 전체 노드 중에서 최대값인 힙
  • 트리의 모든 노드가 자식 노드보다 큰 값을 가짐
  • 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
  • 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
  • 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가짐

힙에서 삭제 및 삽입 연산

배열을 이용한 힙의 구현

• 배열을 이용한 힙의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
  • 연결 리스트보다 실행 속도 면에서 효율적임
  • 기억장소 측면에서도 장점을 가짐
• 힙의 노드 삭제

typedef struct heap {
	int heap[MAX_SIZE];
	int size;
} heap;

int min_heapDelete(heap *h) {
	int parent, child;
	int data, temp;

	data = h -> heap[1];
	temp = h -> heap[(h->size)--];
	parent = 1;
	child = 2;

	while(child <= h -> size) {
		if((child < h -> 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 data;
}

• 힙의 노드 삽입

void min_heapInsert(heap *h, int data) {
	int i;
	i = ++(h -> size);
	
	while((i != 1) && (data < h -> heap[i/2])) {
		h -> heap[i] = h -> heap[i/2];
		i /= 2;
	}
	h -> heap[i] = data;
}