사용자 도구

사이트 도구


알고리즘:우선순위큐

우선순위큐

개요

  • 이진트리를 만들면서 우선순위를 고려하여 업데이트를 한다.
  • Max Heap인 경우 트리의 루트에 있는 것이 가장 큰 값이 된다.
  • Push
    • 트리의 맨 마지막에 새로운 값을 넣음
    • 트리의 맨 아래쪽부터 위로 올라오면서 순서 변경
    • 트리 전체를 업데이트 하는 것이 아니라 맨 마지막과 연결된 부분만 업데이트 됨
  • Pop
    • 트리의 루트에 있는 것을 리턴
    • 트리의 맨 마지막에 있는 것을 루트로 옮김
    • 트리의 루트부터 아래로 내려가면서 업데이트

코드

| 우선순위큐 전역선언
int heap[N + 1];  // heap의 최대 개수보다 커야 함. 0번을 사용하지 않음
int maxn = 0;  // 0번 배열은 사용하지 않음 
| 우선순위큐 push
void push (int d) {
    heap[++maxn] = d
    registter int C = maxn, P = maxn / 2;
    while(P > 0) {
        if(heap[P] < heap [C]) {  // 위배조건
            int temp = heap[P];
            heap[P] = heap[C];
            heap[C] = temp;
        }
 
        C = P; P = C / 2;
    }
}
| 우선순위큐 pop
int pop() {
    int ret = heap[1];
    heap[1] = heap[maxn--];
    register int P = 1, L = 2, R = 3, C;
    while( L <= maxn) {
        if(R > maxn) C = L;
        else C = max(L, R);
 
        if(heap[P] < heap[C]) {
            int temp = heap[P];
            heap[P] = heap[C];
            heap[C] = temp;
        }
 
        P = C, L = P * 2; R = L + 1;
    }
}
알고리즘/우선순위큐.txt · 마지막으로 수정됨: 2018/06/26 15:32 저자 trsprs