힙(Heap)

힙(heap) 이란?

• 완전 이진 트리의 일종이다.
• 우선수위 큐의 한 종류이다.
• 여러 값들 중, 최댓값 혹은 최솟값을 빠르게 찾기 위한 자료구조이다.

힙의 종류

• Max heap(최대 힙)
  부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• Min heap(최소 힙)
  부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  

힙의 구현

• 힙은 완전 이진 트리이며, 배열로 구현 가능
• 배열로 트리를 구현할 경우, 다음의 특징을 갖는다.(배열의 인덱스는 1부터 사용)
  특정 노드의 배열 인덱스가 n일 경우, 부모 노드는 n/2이며, 자식 노드는 n*2(좌측 자식 노드), n*2+1(우측 자식 노드) 이다.

삽입(Max heap)

void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}

삭제(Max heap)

int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}

참고

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://www.geeksforgeeks.org/heap-data-structure/
https://twpower.github.io/137-heap-implementation-in-cpp