Heap

문제2) 자료구조 Heap의 2가지 유형인 Max-heap과 Min-heap을 설명하시오

 

답)

 

1. 완전이진트리를 기본으로 한 자료구조, 힙(Heap)의 개념

• 완전이진트리(Complete Binary Tree)에 있는 Node 중에서 Key 값이 가장 큰 Node나 가장 작은 Node를 찾기 위한 자료구조
• max-heap은 가장 큰 값을 빠르게 찾기 위한 것이고, min-heap은 가장 작은 값을 빠르게 찾기 위한 것

 

2. 가장 큰 값을 빠르게 찾기 위한 Max-heap 상세 설명

가. Max-heap 상세 설명

 

구분	Max Heap(최대 힙)
정의	부모 Node의 키 값이 자식 Node의 키 값보다 항상 크거나 같은 완전이진트리
개념도
개념	Max Heap에 대해서 원소의 개수만큼 삭제 연산을 수행하여 큰 수부터 POP하여 내림차순으로 정렬 수행

 

나. Max-heap 알고리즘 구현 사례

struct MaxHeap { vector<unsigned int> heap; int count; MaxHeap(int n) : heap(n + 1, 0), count(0) {} void insert(unsigned int input) { heap[++count] = input; for (int i = count; i != 1 && heap[i] > heap[i / 2]; i = i / 2) swap(heap[i], heap[i / 2]); } unsigned int pop() { if (count == 0) return 0; int front = heap[1]; swap(heap[1], heap[count]); heap[count--] = 0; for (int i = 1; i * 2 <= count;) { if (heap[i] > heap[i * 2] && heap[i] > heap[i * 2 + 1]) { break; } else if (heap[i * 2] < heap[i * 2 + 1]) { swap(heap[i], heap[i * 2 + 1]); i = i * 2 + 1; } else { swap(heap[i], heap[i * 2]); i = i * 2; } } return front; } };

 

3. 가장 작은 값을 빠르게 찾기 위한 Min-heap 상세 설명

가. Min-heap 상세 설명

 

구분	Min Heap(최소 힙)
정의	부모 Node의 키 값이 자식 Node의 키 값보다 항상 작거나 같은 완전이진트리
개념도
개념	Min Heap에 대해서 원소의 개수만큼 삭제 연산을 수행하여 작은 수부터 POP하여 오름차순으 로 정렬 수행

 

나. Min-heap 알고리즘 구현 사례

 

struct MinHeap // heap에 들어오는 범위가 1 ~ 2^31 -1 인 경우 { vector<unsigned int> heap; int count; MinHeap(int n) : heap(n + 1, pow(2,31)), count(0) {} void insert(unsigned int input) { heap[++count] = input; for (int i = count; i != 1 && heap[i] > heap[i / 2]; i = i / 2) swap(heap[i], heap[i / 2]); } unsigned int pop() { if (count == 0) return 0; int front = heap[1]; swap(heap[1], heap[count]); heap[count--] = pow(2,31); for (int i = 1; i * 2 <= count;) { if (heap[i] > heap[i * 2] && heap[i] > heap[i * 2 + 1]) { break; } else if (heap[i * 2] < heap[i * 2 + 1]) { swap(heap[i], heap[i * 2 + 1]); i = i * 2 + 1; } else { swap(heap[i], heap[i * 2]); i = i * 2; } } return front; } };

 

4. 효과적 사용을 위한 힙정렬 알고리즘의 특징 분석

 

구분	주요 내용
Memory 사용 공간	n개의 원소에 대해 n개의 메모리 공간 사용 크기 n의 Heap 저장공간
연산시간	Heap 재구성 연산시간 1) n개의 Node에 대해 완전 이진트리는 log2(n+1)의 Level을 가지므로 Heap 구성 평균시간은 O(log n) 2) n개의 Node에 대해 n번의 Heap 재구성 작업 수행
평균 시간 복잡도	O(n log n)
비교 회수	2n log n
장점	다른 정렬들에 비해 최악의 연산시간일 경우에도 O(n log n)으로 적게 듦 추가적인 메모리를 필요로 하지 않음
단점	데이터 구조에 따라서 다른 정렬보다 조금 늦게 정렬될 수도 있음

---

 

공감과 댓글은 아이티신비에게 큰 힘이 됩니다.

블로그 글이 유용하다면 블로그를 구독해주세요.♥