Heap
- 힙은 자료구조의 일종으로 우선 순위 큐를 위해 만들어졌다.
- 우선 순위 큐 : 우선순위의 개념에 큐를 도입한 자료구조
- 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다.
- 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 사용된다.
- 우선 순위 큐는 배열, 연결 리스트, 힙으로 구현한다.
개념
- Tree의 형식을 취하고 있으면 Tree 중에서도 배열을 기반으로 한
완전 이진 트리(Complete Binary Tree)
이다 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
- 중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음)
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
힙 종류
최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
힙의 구현
- 힙을 저장하는 표준적인 자료구조는
배열
이다. - 구현을 쉽게 하지 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
부모 노드와 자식 노드 관계
왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2
힙의 삽입
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
- 새로운 노드를 부모 노드들과 교환
void insert_max_heap(int x) {
// 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
maxHeap[++heapSize] = x;
for (int i = heapSize; i > 1; i /= 2) {
// 마지막 노드가 자신의 부모 노드보다 크면 swap
if (maxHeap[i/2] < maxHeap[i]) {
swap(i/2, i);
} else {
break;
}
}
}
부모 노드는 자식 인덱스의 /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; } else if (maxHeap[i*2] > maxHeap[i*2+1]) { // 왼쪽 노드가 더 큰 경우, swap swap(i, i*2); } else { // 오른쪽 노드가 더 큰 경우 swap(i i*2+1); i = i*2+1; } } return item; }
'CS > Data Structure' 카테고리의 다른 글
복잡도 (0) | 2024.03.17 |
---|---|
Stack & Queue (1) | 2024.03.14 |
LinkedList (0) | 2024.02.20 |
Array (1) | 2024.02.16 |