데이터에서 최대값(혹은 최소값)을 빠르게 찾을 수 있는 자료구조
우선순위 큐를 위해 만들어진 자료구조
우선 순위가 높은 데이터가 root에 위치한다
최대 힙(Max Heap)과 최소 힙(Min Heap)이 있다
반 정렬 상태
중복된 값 허용 (이진 탐색 트리는 중복값 허용X)
왼쪽 자식 index = (부모 index) 2
오른쪽 자식 index = (부모 index) 2 + 1
부모 index = (자식 index) / 2
<최대 힙 예시>
<최대 힙 삽입 구현>
void insert_max_heap(int x) {
maxHeap[++heapSize] = x;
// 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
for( int i = heapSize; i > 1; i /= 2) {
// 마지막 노드가 자신의 부모 노드보다 크면 swap
if(maxHeap[i/2] < maxHeap[i]) {
swap(i/2, i);
} else {
break;
}
}
}
부모 노드는 자신의 인덱스의 1/2 이므로, 비교하고 자신이 더 크면 swap하는 방식
<최대 힙 삭제 구현>
int delete_max_heap() {
if(heapSize == 0) // 배열이 비어있으면 리턴
return 0;
int item = maxHeap[1]; // 루트 노드의 값을 저장
maxHeap[1] = maxHeap[heapSize]; // 마지막 노드 값을 루트로 이동
maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드 0 초기화
for(int i = 1; i*2 <= heapSize;) {
// 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝
if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
break;
}
// 왼쪽 노드가 더 큰 경우, swap
else if (maxHeap[i*2] > maxHeap[i*2+1]) {
swap(i, i*2);
i = i*2;
}
// 오른쪽 노드가 더 큰 경우
else {
swap(i, i*2+1);
i = i*2+1;
}
}
return item;
}