우선순위 큐를 위해 만들어진 자료구조
우선순위 큐(Priority Queue)?
우선순위
의 개념을 큐에 도입한 자료구조
데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다!
최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
(이미지 출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html)
우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.
(이미지 출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html)
배열
이다.ex
루트 노드(1)의 오른쪽 노드 번호는 항상 3)
(이미지 출처 : https://ipwag.tistory.com/86)
왼쪽 자식 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;
}
}
}
부모 노드는 자신의 인덱스의 /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;
}
// 오른쪽 노드가 더 큰 경우, swap
else {
swap(i, i*2+1);
i = i*2+1;
}
}
return item;
}
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Heap.md
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html