📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.

우선순위 큐

• 순서대로 기다리고 있는 자료들을 저장
• 가장 먼저 입력된 자료가 가낭 먼저 꺼내지는 것이 아니라, 우선순위가 가장 놈은 자료가 가장 먼저 꺼내짐
• 힙(heap) 트리에 저장

힙

가장 큰 원소를 찾는데 최적화된 이진 트리

• 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 O(lgN)에 수행
• 표준 라이브러리에 포함

힙의 대소관계 규칙
부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상
-> 트리에서 가장 큰 원소는 항상 트리의 루트에 있음

힙의 모양 규칙
트리의 높이를 항상 일정하게 유지하기 위해 구조에 제약을 둠

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져야 함

힙의 구현

vector<int> heap;

• A[i] 의 왼쪽 자손 : A[2*i+1]
• A[i] 의 오른쪽 자손 : A[2*i+2]
• A[i] 의 부모 : A[(i-1)/2]

원소 삽입

void push_heap(vector<int>& heap, int newValue) {
	heap.push_back(newValue);
    int idx = heap.size() - 1;
    while(idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
    	swap(heap[idx], hea[[idx - 1) / 2]);
        idx = (idx - 1) / 2;
    }
}

1. 모양 규칙을 먼저 만족시킴 - 새 노드를 heap[] 의 맨 끝에 추가
2. 마지막에 추가한 새 원소를 자신의 부모 노드와 비교
3. 부모 노드가 새 원소보다 작다면 위치를 바꿈 - 새 원소가 더 크거나 같은 원소를 가진 부모 노드를 만나거나, 루트에 도달할 때까지 반복

최대 원소 꺼내기

void pop_heap(vector<int>& heap) {
	heap[0] = heap.back();
    heap.pop_back();
    int here = 0;
    while(true) {
    	int left = here * 2 + 1;
        int right = here * 2 + 2;
        if(left >= heap.size()) break;
        int next = here;
        if(heap[next] < heap[left]) next = left;
        if(right < heap.size() && heap[next] < heap[right])
        	next = right;
        if(next == here) break;
        swap(heap[here], heap[next]);
        here = next;
    }
}

📍 배열의 최대 원소는 배열의 첫 원소

1. 마지막 노드의 원소를 루트에 덮어쓰고 노드를 지움
2. 두 자식 노드 중 더 큰 원소를 가진 노드와 루트를 바꿈 - 트리의 바닥에 도달하거나, 두 자손이 모두 자기 자신 이하의 원소를 갖고있을 때까지 반복