🌟 힙(Heap)이라는 완전 이진트리(Complete Binary Tree)의 형태를 가지며 일정한 조건을 만족하는 자료구조
데이터 구조 중 하나
힙의 특성에 따라 가장 높은(또는 낮은) 우선순위를 가진 노드가 항상 루트 노드에 위치
💥 자료구조에서 힙은 메모리의 힙이 아니고 우선순위 큐의 힙을 말하는 것
일반적으로 우선순위 큐를 구현하는데 사용됨
👉 즉, 힙트리는 삽입, 삭제, 특히 최댓값 또는 최솟값 검색을 빠르게 수행할 수 있는 효율적인 자료구조
b. 힙트리의 종류
1) 최대 힙(Max Heap)
부모 노드는 자식 노드보다 항상 크거나 같은 값. 따라서 가장 큰 요소가 루트에 위치
➡ 예제에서는 요걸 사용할 것임
2) 최소 힙(Min Heap)
부모 노드는 자식 노드보다 항상 작거나 같은 값. 따라서 가장 작은 요소가 루트에 위치
c. 힙트리의 구조
마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있음 (완전 이진 트리)
마지막 레벨에 노드가 있으면 항상 왼쪽부터 채우기
힙트리 구조
d. 힙트리 법칙
법칙 1 : 부모노드가 가진 값은 항상 자식 노드보다 크다
법칙 2 : 노드 개수를 알면 트리 구조는 무조건 확정
1법칙 / 2법칙
e. 힙트리 구현
👉 동적배열을 이용해 힙트리를 구현한다
배열을 이용해서 구현하면 노드 번호에 대한 규칙성이 생겨서 수식으로 표현할 수 있음
배열로 생성시 부여되는 인덱스 번호 / 코드 생성시 종종 사용하는 수식임 (중요)
1) 새로운 값 추가하기
31이라는 값을 추가한다면
구조 2법칙에 의해 트리의 자식 가장 왼쪽부터 넣어주고
1법칙을 지키기 위해 위로 도장깨기를 함
1. 31값 을 왼쪽부터 넣어주고
2. 도장깨기
2) 최대값 꺼내기
32이라는 최대값 제거
1법칙에 의해 구조부터 맞춰주고 (가장 왼쪽에 있는 값 먼저 머리로 올리고)
아래로 도장깨기를 한다
1. 31제거
2. 14를 젤 위로 올림
3. 아래로 도장깨기 함 / 변경된 모습
4. 우선순위 큐 (priority_queue)
a. 우선순위 큐란?
🌟 데이터의 우선순위에 따라 삽입, 삭제, 검색을 수행하는 추상적인 자료구조
힙이나 이진 검색 트리(BST) 등을 사용하여 우선순위 큐를 구현할 수 있음
💙 다른 자료구조보다 우선순위 큐 사용하는 이유
정렬되지 않은 숫자들이 들어있는 배열에서 가장 크거나 작은 값을 구하려면 정렬하거나(NlogN), 어떤 값과 비교(N) 해서 구하는 방법이 있는데
👉 그 두가지 방법보다 우선순위 큐가기준을 정해서 어떤 값을 추출할 때 유용함
b. 힙 트리와 우선순위 큐의 차이점
a) 개념적 차이점
힙트리 : 이진트리 형태로 데이터 요소가 특정 조건을 만족하는 자료구조
우선순위 큐 : 데이터 요소가 특정 조건을 가지고 가장 높은 우선순위를 가진 요소가 먼저 꺼내지는 자료구조
b) 용도
힙트리 : 데이터를 효율적으로 저장(삽입), 최대/최솟값을 빠르게 찾기 위함(삭제)
우선순위 큐 : 데이터의 우선순위에 따라 삽입, 삭제, 검색을 수행
c) 구현 방법
힙트리 : 배열이나 리스트
우선순위 큐 : 힙트리나 이진 검색 트리를 사용해 구현 (큐의 동작 특성에 따라 선택)
👉 즉, 힙트리는 우선순위 큐를 구현하는데 사용되는 하나의 방법이고
우선순위 큐는 데이터의 우선순위를 기반으로 작업을 수행하는 추상적인 자료구조
c. 우선순위 큐 구현하기
<우리가 만들 목표>
표준은 priority_queue
📘 우선순위 큐 : 힙트리로 구현
template<typename T> //데이터는 t타입
class PriorityQueue {
public:
//데이터 삽입 및 우선순위 변경
void push(const T& data) {
//1. 힙 구조부터 맞추기
_heap.push_back(data);
//2. 도장깨기 시작
int now = static_cast<int>(_heap.size()) - 1; //현재 인덱스
//3. 루트 노드까지 반복
while (now > 0) {
int next = (now - 1) / 2; //부모 인덱스
if (_heap[now] < _heap[next]) { //부모 노드보다 수가 작으면
break;
}
//데이터 교체
::swap(_heap[now], _heap[next]);
now = next;
}
}
//데이터 제거하기 (최대값 꺼내기)
void pop() {
_heap[0] = _heap.back(); //먼저 0번에 마지막 데이터(Heap.back())를 넣어주고
_heap.pop_back(); //맨 마지막 데이터 제거
int now = 0;
while (true) {
int left = 2 * now + 1; //인덱스 공식에 의한 위치
int right = 2 * now + 2;
//이진트리 모양을 벗어나는 모습일 경우(리프) 예외처리
if (left >= (int)_heap.size()) {
break;
}
int next = now;
//왼쪽 비교 (나(next)랑 왼쪽이랑 비교했을때)
if (_heap[next] < _heap[left]) //더 작다면
next = left; //왼쪽으로
//둘 중 승자를 오른쪽과 비교 (혹시 모르니까 체크)
if (right < _heap.size() && _heap[next] < _heap[right])
next = right;
//왼쪽/오른쪽 둘 다 현재 값보다 작으면 종료
if (next == now)
break;
//아니면 위치를 변경해준다
::swap(_heap[now], _heap[next]);
now = next;
}
}
//최고 데이터 검색
T& top() {
//힙트리 관점에서 제일 큰 값은 0번 인덱스에 있음
return _heap[0];
}
//존재 유무
bool empty() {
return _heap.empty(); //벡터의 empty 함수 활용
}
public:
vector<T> _heap; //데이터의 사이즈가 유동적이니 벡터로 관리
};
💥 pop/top 두개인 이유는 예외처리 관점에서 그렇다
✨ 예제 실행
vector<int> v;
PriorityQueue<int> pq;
pq.push(10);
pq.push(40);
pq.push(20);
pq.push(50);
pq.push(30);
int value = pq.top(); //50
pq.pop();
int value2 = pq.top(); //40
😀 기본적으로 위 원리에 대해서 잘 알아둬야 함
d. 우선순위큐의 시간 복잡도
각 함수에 대한 시간 복잡도는 다음과 같음
즉, 삽입 후 우선순위를 변경하거나 데이터를 제거할 때
트리의 높이에 비례하는 시간이 소요됨
트리는 2배로 데이터 공간이 늘어나고 줄어들기 때문에 log n 의 시간이 소요된다
✒ 즉 이렇게 요약할 수 있음 (아마존 문제였다 ㅎㄷㄷ)
🌟 우선순위 큐의 총 시간 복잡도가 O(log n)인 이유는 힙을 기반으로 구현되기 때문
힙은 요소 삽입, 삭제, 우선순위 변경 시 트리의 높이에 비례하여 재배치되기 때문에 O(log n)의 시간이 소요 (이는 힙의 특성에 기인) 따라서 우선순위 큐의 모든 연산에 대해 O(log n)의 시간 복잡도가 유지됨
e. 우선순위 큐의 제일 작은 값
트릭 : 사용시 음수를 넣어서 대소 관계를 반대로 만들어 사용할 수 있음
판별 객체 사용(Predicate)
1) Predicate인 이름으로 판별객체를 생성후 객체로 사용해 (type)
2) 우선순위 큐를 생성할 때 판별객체를 인수로 받아주고
T타입인 Predicate는 less<T>라는 구조체로 생성
💙 less, greater 구조체
이 구조체는 오퍼레이터 오버로딩을 이용해 ()라는 오퍼레이터를 실행할 때, 그 값 중 크거나 작은쪽을 내보내게 만들어준 구조체
less를 사용하면 비교시 가장 큰 값이 튀어나옴
greater는 가장 작은값이 나온다 👉 그래서 less, greater로 생성된 Predicate라는 객체가 그 역할을 대신하는 것
