이 글의 목차
숨기기
1. 기본 아이디어
지난번에는 특정 id에 해당하는 원소를 찾기위해 힙의 첫번째 원소부터 순차적으로 반복문을 돌리면서 해당하는 인덱스를 얻었습니다. 하지만, 이 과정을 없애버릴 수 있습니다. 따로 테이블에 특정 id에 해당하는 원소가 Heap의 몇 번 인덱스에 존재하는지를 기록하고 관리하면 됩니다. 이렇게 되면 O(N)이 걸렸던 것을 O(1)로 줄일 수 있습니다. 나머지 부분은 지난 시간의 아이디어와 동일합니다. 그래서 결과적으로 O(1+logN)==> O(logN)만에 특정 원소를 삭제하고 업데이트 할 수 있습니다.
2. 실제 구현 코드
저는 특정 id에 해당하는 원소가 Heap의 몇 번 인덱스에 존재하는지를 Unordered Map을 활용해서 기록했습니다. 참고로 id의 범위가 배열로 표현할 수 있을 만큼 작다면, 그냥 int형 배열을 쓰는게 당연히 더 효율적입니다. 그렇지만 실제 문제에서는 id의 범위가 “1억이하 자연수” 같이 크게 주어질 수 있는데 이 때는 Unordered Map을 쓰던지 아니면 그냥 Map을 쓰던지 해야합니다.
실제로 구현할 때 특히 신경써야 하는 부분은 index를 갱신하는 것입니다. 새 원소가 push될 때 새 원소에게 index를 부여해야 하고, 원소가 pop될 때 그 원소의 index를 없애줘야 합니다. 또한 up,down연산에서 원소들이 swap될 때 index도 바뀌도록 처리해주는 걸 절대로 까먹어서는 안 됩니다.
#include<stdio.h> //힙 응용(특정원소 삭제 O(logN), 업데이트 O(logN)
#include<unordered_map>
using namespace std;
const int MAX_N = 1000;
const int MAX_ID_NUM = 10000;
struct Student {
int p1, p2, id;
};
Student heap[MAX_N];
int heapSize = 0;
unordered_map<int, int> indexMap; <em>//indexMap[학생 아이디]:힙에 몇번째 인덱스에 이 id 가진 학생이 존재하는지 저장</em>
void heapInit() {
heapSize = 0;
indexMap.clear();
}
<em>//p1큰게 앞에, 같다면 p2작은게 앞으로</em>
int cmpStudent(int index1, int index2) {
return (heap[index1].p1 > heap[index2].p1) || ((heap[index1].p1 == heap[index2].p1) && (heap[index1].p2 < heap[index2].p2));
}
void up(int index) {
int cur = index;
int parent = (cur >> 1);
while (parent > 0 && cmpStudent(cur, parent)) {
Student temp = heap[cur];
heap[cur] = heap[parent];
heap[parent] = temp;
<em>//인덱스 갱신</em>
indexMap[heap[cur].id] = cur;
indexMap[heap[parent].id] = parent;
cur = parent;
parent = (cur >> 1);
}
}
void down(int index) {
int cur = index;
int child = (cur << 1);
while (child <= heapSize) {
if (child + 1 <= heapSize) {
child = cmpStudent(child, child + 1) ? child : child + 1;
}
if (cmpStudent(cur, child))break;
Student temp = heap[cur];
heap[cur] = heap[child];
heap[child] = temp;
<em>//인덱스 갱신</em>
indexMap[heap[cur].id] = cur;
indexMap[heap[child].id] = child;
cur = child;
child = (cur << 1);
}
}
void push(Student data) {
heap[++heapSize] = data;
<em>//새로 추가된 원소 인덱스 저장</em>
indexMap.insert(make_pair(data.id, heapSize));
up(heapSize);
}
Student pop() {
Student ret = heap[1];
indexMap.erase(ret.id); <em>//삭제 원소는 인덱스 0으로 바꿔주자</em>
if (heapSize == 1) {
heapSize--;
}
else {
heap[1] = heap[heapSize--];
indexMap[heap[1].id] = 1; <em>//인덱스 갱신</em>
}
down(1);
return ret;
}
<em>//id에 해당하는 학생 힙에서 삭제하기</em>
void remove(int id) {
<em>//1.해당 학생의 힙 인덱스 구하기</em>
int index = indexMap[id];
<em>//2.그 노드의 우선순위 최대로 만들어주기</em>
heap[index].p1 = 99999; heap[index].p2 = -1;
<em>//3.루트로 올려주자</em>
up(index);
<em>//4. pop해주자</em>
pop();
}
void update(int id, int newP1, int newP2) {
<em>//1.해당 학생의 힙 인덱스 구하기</em>
int index = indexMap[id];
<em>//2.그 노드 우선순위 변화시키기</em>
heap[index].p1 = newP1; heap[index].p2 = newP2;
<em>//3.위로 보내기</em>
up(index);
<em>//4. 아래로 보내기</em>
down(index);
}
int main(void) {
heapInit();
int p1 = 1; int p2 = 2; int id = 10;
Student student;
for (int i = 0; i < 10; i++) {
student.p1 = p1; student.p2 = p2; student.id = id;
push(student);
if (i & 1)p1++;
if (p2 == 1)p2 = 2;
else p2--;
id--;
}
<em>//pop하면 이 순서임</em>
<em>/*
p1: 5, p2: 1, id: 1
p1: 5, p2: 2, id: 2
p1: 4, p2: 1, id: 3
p1: 4, p2: 2, id: 4
p1: 3, p2: 1, id: 5
p1: 3, p2: 2, id: 6
p1: 2, p2: 1, id: 7
p1: 2, p2: 2, id: 8
p1: 1, p2: 1, id: 9
p1: 1, p2: 2, id: 10
*/</em>
<em>//id=6인 원소 삭제 해보자</em>
remove(6);
<em>/*
p1: 5, p2: 1, id: 1
p1: 5, p2: 2, id: 2
p1: 4, p2: 1, id: 3
p1: 4, p2: 2, id: 4
p1: 3, p2: 1, id: 5
p1: 2, p2: 1, id: 7
p1: 2, p2: 2, id: 8
p1: 1, p2: 1, id: 9
p1: 1, p2: 2, id: 10
*/</em>
<em>//id=5인 원소 update 해보자.</em>
update(5, 10, 1);
for (; heapSize != 0;) {
Student ret = pop();
printf("p1: %d, p2: %d, id: %d\n", ret.p1, ret.p2, ret.id);
}
printf("\n");
<em>/*
p1: 10, p2 : 1, id : 5
p1 : 5, p2 : 1, id : 1
p1 : 5, p2 : 2, id : 2
p1 : 4, p2 : 1, id : 3
p1 : 4, p2 : 2, id : 4
p1 : 2, p2 : 1, id : 7
p1 : 2, p2 : 2, id : 8
p1 : 1, p2 : 1, id : 9
p1 : 1, p2 : 2, id : 10
*/</em>
}
