[자료구조][알고리즘] 히프(heap) - 최대 히프(max heap), 최소 히프(min heap)

히프(heap)

히프는 우선순위 큐(priority queue)를 구현하는 데 자주 사용된다. 

우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다.

또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다.

히프 또한, 완전 이진 트리(complete binary tree) 이다.

 

히프에는 최대 히프와 최소 히프가 있다. 

최대(최소)트리[max(min) tree)]는 각 노드의 키 값이( 자식이 있다면) 그 자식의 키값보다 작지(크지) 않은 트리이다.

최대 히프(max heap)는 최대 트리이면서 완전 이진 트리이다.
최소 히프(min heap)는 최소 트리이면서 완전 이진 트리이다.

최대 히프에서의 삽입

새 노드에서 시작해서 루트 쪽으로 올라가는(bubbling up) 방법을 사용

void push(element item, int *n)
{ /*현재 사이즈가 n인 최대 트리에 item을 삽입*/
	int i;
	if (HEAP_FULL(*n)) {
		fprintf(stderr, "The heap is full.\n");
		exit(EXIT_FAILURE);
	}
	i = ++(*n);
	while ((i != 1) && (item.key > heap[i / 2].key)) { 
		heap[i] = heap[i / 2];  //왼쪽 자식에 삽입
		i /= 2;
	}
	heap[i] = item;
}

최대 히프에서의 삭제

a) 제일 큰것을 뽑는다.(즉, root) 
b) 제일 마지막 값을 root로 올리고 그 후 위에서 내려간다.
c) 최대 히프를 재구성 해준다.

element pop(int *n)
{ /*히프에서 가장 큰 값을 제거 해준다.(root)*/
	int parent, child;
	element item, temp;
	if (HEAP_EMPTY(*n)) {
		fprintf(stderr, "The heap is empty\n");
		exit(EXIT_FAILURE);
	}
	item = heap[i]; //가장 큰 값을 저장해준다.
	/*가장 마지막 값을 root로 올려 재조정 해준다.*/
	temp = heap[(*n)--];
	parent = 1;
	child = 2;
	while (child <= *n) {
		/*현재 부모의 더 큰 자식을 찾는다.*/
		if (child < *n) &(heap[child].key < heap[child + 1].key)
			child++;
		if (temp.key >= heap[child].key) break;
		/*그 다음 낮은 레벨로 이동한다.*/
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}
	heap[parent] = temp;
	return item;
}

 

트리 관련 알고리즘

 - [프로그래밍/자료구조] - [자료 구조][알고리즘] 트리(tree)

 - [프로그래밍/자료구조] - [자료 구조][C언어] 이진 트리 순회(traversal) - 중위(inorder), 전위(preorder),후위(postorder) 순회