힙(heap)이란

• 완전 이진트리를 기반으로 만들어진다.
• 우선순위 큐를 위하여 만들어졌다.
• 형제들의 순서는 상관없이 부모와 자식의 순서 규칙만 정해져 있다.
• 힙은 중복을 허용한다.

힙(heap)의 종류

1. 최대 힙(max heap)

형제 노드 끼리의 순서는 상관 없고 부모 노드의 값이 자식 노드의 값보다 크거나 같다..

2. 최소 힙(min heap)

형제 노드 끼리의 순서는 상관 없고 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

---

배열을 이용한 최대 힙 구현하기

배열을 이용해 이진트리를 구성하는 방법

• 루트의 인덱스 = 1
• 부모의 인덱스 = (자식의 인덱스) / 2
• 왼쪽 자식 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1

push pop 이해하기

#define parent (i >> 1)
#define left (i << 1)
#define right (i << 1 | 1)

1. push

void push(int x) {
		data[++size] = x; // 데이터를 삽입합니다.
		for (int i = size; parent != 0 && data[parent] < data[i]; i >>= 1) {
			std::swap(data[parent], data[i]);
		}
	}

배열의 맨 끝에 원소를 추가해준 후 부모와 자기 자신을 비교하며
부모가 자기 자신 보다 작을 경우 swap을 해주며 최대 힙의 조건을 만족해 나갑니다.

2. pop

void pop() {
		assert(size != 0);
		data[1] = data[size--];
		for (size_t i = 1; left <= size;) {
			if (left == size || data[left] > data[right]) { //왼쪽 자식 하나만 가지고 있
				if (data[i] < data[left]) { // 거나 왼쪽 자식이 오른쪽 자식 보다 클 경우
					std::swap(data[i], data[left]);
					i = left;
				} else {
					break;
				}
			} else {
				if (data[i] < data[right]) {
					std::swap(data[i], data[right]);
					i = right;
				} else {
					break;
				}
			}
		}
	}

1. 루트 노드를 삭제하고 완전 이진트리의 조건을 만족하기 위해 맨 뒤에 있는 노드를 루트노드로 지정한다.
2. 왼쪽 자식과 오른쪽 자식 중에 더 크면서 부모보다 큰 값을 부모노드와 swap을 진행 한다.