[DS] Heaps

5.6.1 Heap ADT

• Max tree : parent의 값이 child의 값보다 작지 않음(크거나 같음) & complete binary tree(왼쪽 부터 꽉 차 있음)
• Min tree : parent의 값이 child의 값보다 크지 않음(작거나 같음) & complete binary tree(오른쪽부터 꽉 차 있음)

• Array 로 표현할 때 [0] 사용 X. (표현할 때 2n+i) 형식이기에.
• Heap 에서
  • min tree 의 root는 tree에서 가장 작은 값.
  • max tree 의 root는 tree에서 가장 큰 값

5.6.2 Priority Queues

• Heap 은 priority queues(우선순위 큐) 구현에 사용.
• 우선순위 큐는 가장 높은 (or 낮은) 우선순위 원소 삭제.
• 임의의 우선순위 가진 원소 삽입 가능
• 시간 복잡도 비교

	삽입	삭제
Unordered Array	O(1)	O(n)
Unordered Linked List	O(1)	O(n)
Sorted Array	O(n)	O(1)
Sorted Linked List	O(n)	O(1)
Max Heap	O(log₂n)	O(log₂n)

→ Max Heap 의 (log₂n)은 depth.

5.6.3 Insert Into A Max Heap

• 과정
  1. 맨 아래 삽입
  2. parent와 비교
     • 작으면 그대로. break
     • 크거나 같으면 위치 교환
  3. root 까지 2의 과정 반복 (root = 1에 도착하면 break)
• Declaration

#define MAX_ELEMENTS 200 // maximum heap size+1
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1) // 199면 꽉 참
#define HEAP_EMPTY(n) (!n)

typedef struct {
	int key;
	// other field
} elements;
element heap[MAX_ELEMENTS]; // 1 ~ 199만 사용
int n = 0;

[Program 5.13] Insertion into max heap

void insert_max_heap (element item, int *n) {
	// 현재 size 가 n인 heap에 item 삽입
	int i;
	if(HEAP_FULL(*n)) {
		fprintf(stderr, "The heap is full. \n");
		exit(1);
	}
	i = ++(*n);
	while ((i != 1) && (item.key > heap[i/2].key)) { // root 가 아니고 parent 보다 크면
		heap[i] = heap[i/2]; // 위치 교환
		i /= 2;
	}
	heap[i] = item; // 맞는 위치에 item 값 넣기.
}

• 시간 복잡도 : O(log₂n)

5.6.4 Delete From A Max Heap

• 과정
  • 항상 heap 의 root 제거.
  • 가장 마지막 leaf 를 root로 설정.
  • 그 후 교환해 아래로 내리기

[Program 5.14] : Deletion from a max_heap

element delete_max_heap (int *n) {
	// heap의 가장 상위의 값 삭제
	int parent, child;
	element item, temp;
	if (HEAP_EMPTY(*n)) {
		fprintf(stderr, "The heap is empty");
		exit(1);
	}
	// 가장 상위의 값 저장
	item = heap[1]; // root 삭제
	// 마지막 node 이용해 heap 다시 균형 잡기
	temp = heap[(*n)--]; // 마지막 node 저장 후 감소.
	parent = 1;
	child = 2;
	while (child <= *n) { 
		// 현 parent 보다 높은 child 찾기
		if ((child <= *n) && (heap[child].key < heap[child+1].key)) 
			child++;
		if (temp.key >= heap[child].key) break; // root 가 제일 큼
		// 더 낮은 level 로 이동
		heap[parent] = heap[child];
		parent = child; // x2 씩 증가
		child *= 2; // x2 씩 증가
	}
	heap[parent] = temp;
	return item;
}

→ 시간 복잡도 : O(log₂n)