Heap에서 원하는 노드의 값 수정하기 (index를 관리하는 Heap 구현)

이전 프로 기출문제 댓글중에서 잠시 언급한적이 있는 "원하는 노드 값을 수정할 수 있는 Heap 자료구조"에 대한 내용입니다.

 

일단 우리가 흔히 알고있는 Heap (priority_queue)의 구현체는 다음과 같습니다.

struct Heap {
  int n;
  int v[100009];
  void inil() {
    n = 1;
  }
  void push(int value) {
    v[n] = value;
    n++;
    update(n - 1);
  }
  int pop() {
    n--;
    int res = v[1];
    v[1] = v[n];
    v[n] = res;
  
 
 
    downdate(1);
 
 
    return res;
  }
  int top() { return v[1]; }
  void update(int ti) {
    //update
    while (ti > 1) {
      int ri = ti / 2;
      if (v[ri] > v[ti]) {
        int tmp = v[ri];
        v[ri] = v[ti];
        v[ti] = tmp;
        ti = ri;
      }
     else
        break;
    }
  }
  void downdate(int ti) {
    //downdate
    while (ti < n) {
      int pi = ti * 2;
      int qi = ti * 2 + 1;
      int ri = pi;
      if (pi >= n)break;
      if (qi >= n)ri = pi;
      else {
        if (v[ri] > v[qi])ri = qi;
      }
      if (v[ti] > v[ri]) {
        int tmp = v[ri];
        v[ri] = v[ti];
        v[ti] = tmp;
        ti = ri;
      }
     else
        break;
    }
  }
};

일단 코드에 대한 자세한 설명은 생략하기로 하고...heap이 동작하는 대략적인 흐름은 이렇습니다.

1. push

 - Heap 이진트리의 제일 뒤쪽에 넣고

 - 그 노드가 올라갈 수 있는 최대한으로 올려보낸다.

 

 

2. pop

 - Heap 이진트리의 제일 뒤쪽과 제일 꼭대기를 교환한 뒤

 - 꼭대기로 올라와버린 노드를 아래로 내려보낸다.

 

 

이제 이렇게 구현된 상태에서 "원하는 노드의 값"을 수정할 수 있도록 만들어보고자 합니다.

일단 이런 자료구조를 항상 쓸 수 있는건 아니고 '원하는 노드'가 정확히 무엇인지를 정의할 수 있을 때에만 동작합니다.

예를 들면 뭐 '값을 pid값을 가지는 어떤 노드' 라거나...  'x번째로 삽입했던 어떤 노드'라거나...

pid값을 가지는 노드가 2개 이상 존재할 때는 원하는 노드를 특정시킬 수 없기 때문에 조금 변형을 해야합니다.

 

뭐 아무튼.. 일련의 과정을 통해서 각 노드들에게 0부터 N-1까지 labeling을 해놨다고 해봅시다.

이제 우리가 하고싶은 동작은 다음과같이 정의되게 됩니다.

 

　[i번으로 이름을 붙인 노드의 값을 value로 변경시킨 뒤에도 Heap 자료구조 상태를 유지]

 

 

문제를 너무 일반화시키면 이해가 난해할 수도 있으니 다음과 같은 문제를 생각해봅시다.

 

  배열 a[0], a[1] ... a[n-1]가 있을 때 아래의 query들을 수행

  1) update(i, v) --> a[i] = v로 바꾼다.

  2) get_min() --> a[0]~a[n-1] 중 가장 작은 값을 출력

 

배열의 값이 변하지 않는다면 a[0]~a[n-1]까지 값을 Heap에 다 때려박은 후에 가장 작은 값을 구하면 됩니다.

하지만 update(i,v)는 a[i]값을 v로 바꿔버리길 원합니다. 그럼 Heap에 있던 값을 다 꺼내서 a[i]를 v로 바꾼 뒤 다시 집어넣어야할까요?

아니면 바뀌기 전 a[i]값이 나올때 까지 heap에서 탐색을 수행해야할까요?

 

 

-------------------------------------

 

우리가 원하는 동작을 대략적으로 적어보면 다음과 같습니다.

 

 문제1) a[i]에 해당하는 값이 Heap상에서 어디에 위치하는지를 O(1)만에 알아내고

 

 문제2) 그 노드의 값을 v로 바꿔버리고

 

 문제3) Heap 자료구조를 유지시키도록 노드를 O(log n)만에 영차정차 옮긴다.

 

의 방식으로 동작시키면 원하는 것을 수행할 수 있습니다.

 

그리고 제목에도 적어놨듯이 Heap 내부에서 "index"의 위치를 관리하는 루틴을 추가하면

위의 문제를 해결할 수 있습니다.

 

 

그럼 문제1)부터 해결해봅시다.

heap상에서 노드를 push할 때, 이진트리의 가장 마지막에 쑤셔박는다고 알고있을겁니다.

그럼 i번 노드를 heap에 넣은 뒤, 아무런 노드이동을 하지 않았을 경우 i번 노드의 index는 n (== heap의 size)이 됩니다.

void push(int value, int i){
  v[n] = value;
  v_index[n] = i;
 
 
  index[i] = n;
  // ~~~
 
 
}

그 다음 추가된 노드는 위로 올라갈 수 있을때까지 자기 부모노드랑 swap을 반복하게 됩니다.

이 때 값만 바꾸는것이 아니라 index도 같이 변경시킬 수 있습니다.

void update(int ti){
 
 
  while (ti > 1) {
    int ri = ti / 2;
    if (v[ri] > v[ti]) {
      int tmp = v[ri];
      v[ri] = v[ti];
      v[ti] = tmp;
 
 
      tmp = v_index[ti];
      v_index[ti] = v_index[ri];
      v_index[ri] = tmp;
 
 
      index[v_index[ti]] = ti;
      index[v_index[ri]] = ri;
 
 
      ti = ri;
    }
  }
}

위 코드와 아래 코드에서 v_index 라는 배열, index라는 배열이 하는 일이 뭔지 잘 확인해보면...

v_index[k] = heap의 k번 노드값이 저장되있는 a[i]의 index i값

index[i] = a[i]가 저장되있는 heap의 노드 번호

대충 이런 역할을 하고 있습니다.

 

위 루틴을 조심히..그리고 잘 따라가다보면 index 번호가 swap됨을 확인할 수 있습니다.

 

update()함수에서 한 index 변경 루틴을 그대로 따라서 downdate() 함수에서도 index 변경을 시킬 수 있습니다.

 

void downdate(int ti){
 
 
  while (ti < n) {
    // blabla...
 
 
    if (v[ri] < v[ti]) {
      int tmp = v[ri];
      v[ri] = v[ti];
      v[ti] = tmp;
 
 
      tmp = v_index[ti];
      v_index[ti] = v_index[ri];
      v_index[ri] = tmp;
 
 
      index[v_index[ti]] = ti;
      index[v_index[ri]] = ri;
 
 
      ti = ri;
    }
  }
}

 

이제 무슨 짓을 할 수 있냐면... i가 주어졌을 때 a[i]값이 저장되있는 heap의 노드를 한번에 알 수 있습니다.

그 값은 바로 index[i]이죠.

만약 a[i]값이 value로 변경되었다면 우리는 다음과 같은 방법을 통해 heap 내부적으로도 값의 변경을 반영시킬 수 있습니다.

void update_direct(int i, int value)
{
  v[index[i]] = value;
 
 
}

 

이제 문제2)번 문제도 해결되었습니다. 남은건 저 바뀌어버린 v[index[i]] 노드를 영차정차 옮겨서

heap의 자료구조상태를 유지시키는 일만 남았습니다.

 

 

 

여기 평화로운 Heap 나라에 빨간 노드가 쳐들어왔다고 합시다!.

이 값은 갑작스러운 변화로 인해서 v라는 값으로 바뀌어버렸고

때문에 heap구조를 만족하지 않을 수 도 잇는 위험한 노드입니다.

 

이 친구를 빨리 처리해야하는데... 처리하는 아이디어는 이미 push / pop할 때 이미 모두가 사용했던 방법입니다.

 

push에서는 heap 구조를 만족하지 않는, 제일 마지막에 있는 노드를 다음과같이 처리했습니다.

 - 그 노드가 올라갈 수 있는 최대한으로 올려보낸다.

pop에서는 heap 구조를 만족하지 않는, 제일 위에 있는 노드를 다음과같이 처리했습니다.

 - 꼭대기로 올라와버린 노드를 아래로 내려보낸다.

각각이 update와 downdate에 해당하는 동작입니다.

 

그럼 다음과 같은 짓을 해버리면 모든 문제가 해결될까요?

void update_direct(int i, int value)
{
  v[index[i]] = value;
  update(index[i]);
  downdate(index[i]);
 
 
}

놀랍게도 해결됩니다.!

 

자세한 사항은 솔직히 넘어가고싶은 심정인데...

중요한 포인트만 하나 짚고 넘어가겠습니다.

 

만약 위 함수에서 update보다 downdate를 먼저 호출하면 결과가 달라질까요?

 

비교연산자 < 가 잘 정의되있기만 하면, 새로 변경된 index[i]라는 노드는

무조건 update방향으로만 올라가거나

downdate방향으로 내려가기만하고

두 연산이 동시에 반영되지 않습니다.

 

 

위의 그림은 값이 변경된 i노드가 update되다가 어느순간 downdate로 인해 한칸 아래로 내려간 상황입니다.

만약 이런 상황이 발생했다는건 다음 부등식 조건이 만족됐다는 의미입니다.

(i번노드의 값) < (2번 노드의 값)

&&

(1번 노드의 값) < (i번 노드의 값)

 

즉, (1번 노드의 값) < (2번 노드의 값) 이 되버려서 이미 애초에 heap 구조를 만족하지 않았을 때라는 의미가 되고

따라서 이런 상황은 발생하지 않습니다.

 

downdate 되다가 update되는 경우가 없다는건 자명하므로 생략하겠습니다. It's trivial!

 

 

 

 

 

자 그럼 값이 변경된 빨간 노드는 update로 위로 올라가거나, downdate로 아래로 내려가는 일만 남았습니다.

downdate로 내려가는 경우는 왼쪽에 녹색으로 표시한 크기 3짜리 sub-heap(?)에서 pop연산후 내려가는 노드랑 동작이 똑같습니다.

update로 올라가는 경우는 오른쪽에서 파란색으로 표시한 크기 4짜리 sub-heap(?)에서 push연산 후 올라가는 노드랑 동작이 똑같습니다.

pop과 push연산이 멀쩡히 돌아간다면, 위 두 상황에 대해서도 멀쩡히 돌아갈테고,

결과적으로 heap이 전체적으로 멀쩡하다는 것이 증명됩니다.

 

------------------------------------

 

여하튼, 이렇게 heap에서 노드의 값이 변경되는 상황에 대한 구현은 생각보다 쓸만한데요..

당장 저번 Pro시험에서 '도서관에 책 재고가 0개인 경우는 책을 추천하지 않는다. 하지만 재고가 0개 되는 순간 기록에서 사라져버리는게 아니라, 새로 입고되면 기존의 점수를 유지된 채로 추천이 이루어져야한다.' 뭐 이런상황에 대한 처리를 아주 깔끔하게 구현할 수 있습니다.

 

그리고 무엇보다 query동작에 대응하는 자료구조로서,

Segment Tree같이 고인물 썪은 냄세 풍기는 고오오급(?) 자료구조를 쓰지 않더라도

조금만 생각하면 누구나 떠올릴 수 있는 자료구조라는 점이 장점입니다.

 

 

https://www.acmicpc.net/problem/14427

이 문제가 해당 내용을 대놓고 구현하는 문제입니다.

 

proof by Accept 방식을 통해 자신의 코드의 정당성을 증명해보실 수 있습니다.

 

또한 이번에 올라온 여행상품추천 문제도 이렇게 관리하면

여행지가 팔려나감과 동시에 heap에서 제거시켜버릴 수 있습니다.

 

아래 코드는 여행상품추천 문제는 아니고.. 수열과 쿼리 문제에 대한 코드입니다.

제가 편한대로 구현했기 때문에 위에서 적은거랑 약간 다르긴한데.. 뭐 크게 다르지 않습니다. 아니 그냥 똑같습니다.

 

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
struct Heap {
  int n;
  pii v[100009];
  int index[100009];
  void inil() {
    n = 1;
  }
  void push(int value, int i) {
    v[n] = pii(value, i);
    index[i] = n;
    n++;
    update(n - 1);
  }
  pii pop(int i = -1) {
    int pid = 1;
    if (i != -1) {
      pid = index[i];
    }
    n--;
    pii res = v[pid];
    v[pid] = v[n];
    v[n] = res;
    index[v[pid].second] = pid;
    index[v[n].second] = n;
 
 
    update(pid);
 
 
    return res;
  }
  pii top() { return v[1]; }
  void update_direct(int i, int vv) {
    v[index[i]].first = vv;
    update(index[i]);
  }
  void update(int ti) {
    //update
    while (ti > 1) {
      int ri = ti / 2;
      if (v[ri] > v[ti]) {
        pii tmp = v[ri];
        v[ri] = v[ti];
        v[ti] = tmp;
        index[v[ti].second] = ti;
        index[v[ri].second] = ri;
        ti = ri;
      }
     else
       break;
    }
 
 
    //downdate
    while (ti < n) {
      int pi = ti * 2;
      int qi = ti * 2 + 1;
      int ri = pi;
      if (pi >= n)break;
      if (qi >= n)ri = pi;
      else {
        if (v[ri] > v[qi])ri = qi;
      }
      if (v[ti] > v[ri]) {
        pii tmp = v[ri];
        v[ri] = v[ti];
        v[ti] = tmp;
        index[v[ti].second] = ti;
        index[v[ri].second] = ri;
        ti = ri;
      }
     else
       break;
    }
  }
};
Heap hop;
int n;
int main() {
  int i, j, k;
  scanf("%d", &n);
  hop.inil();
  for (i = 1; i <= n; i++) {
    scanf("%d", &j);
    hop.push(j, i);
  }
  scanf("%d", &n);
  while (n--) {
    int type;
    scanf("%d", &type);
    if (type == 2) {
      printf("%d\n", hop.top().second);
    }
    else {
      scanf("%d %d", &i, &j);
      hop.update_direct(i, j);
    }
  }
}