백준1927 (SILVER 2) - 최소 힙

[SILER 1] 최소 힙

10만개 연산 처리 > O n제곱으로 처리 불가 -> 삽입 삭제 각연산이 로그 n 이어야함. 과거 배운 자료구조에서 그 구현에 대한 정보를 얻을 수 있었다.

관련된 정보를 몇개 적어두겠다.

힙

• 완전 이진트리
• 1차원 배열로 구현
• 최댓값, 최솟값 빠르게 찾기 위한
• 우선순위 큐 같은 구현에도 사용

타 코드 참고 사항

#include <queue>
std::priority_queue <T, std::vector<T>, compare 함수>
//container adapter라 그런지 컨테이너도 선택함(기본 벡터, 덱도가능)
// 뒤의 컴페어 함수는 참인 경우 그대로. 아니면 뒤집음
//greater<T>를 주면 오름차순 정렬(top에 작은게 오도록)

를 사용하면 stl로 빠르게 구현 가능.

코드

``` c++ //log n으로 모두 처리해야함.

//어려웠다… 단순 구현인데 똥을 좀 많이쌌다. //C++에서 힙을 사용할 방법은??

#include #include #include

int hip[100001]; int size = 0;

void deletemin() {

if(size == 0){ std::cout « 0«‘\n’; return; } std::cout « hip[1] « ‘\n’; hip[1] = hip[size]; hip[size] = 0; size–;//0에서 마이너스되는걸 생각못했네.. 이렇게뭐 넣을땐 음수되면 클나지않ㅇ르까생각해 //이와 같은 전역 변수(처럼 ㅆ는친구들) 이상한 값으로 빠지거나, 제때 초기화 안하는 것 조심하기.

int i= 1;

while(i2 <= size) { int left = i2; int right = i*2 +1; int minposition = 0; if(size < right){ minposition = left; } else if(hip[left]<=hip[right]) { minposition = left; } else { minposition = right; } //인덱스를 오버하는 경우를 제하면서, 어떻게 left, right 자식 선택하는것을 //짤 것인가??

if(hip[minposition] <hip[i]){//다운 힙은 '힙성질이 만족될때까지'
  std::swap(hip[minposition],hip[i]);
}else {
  break;
}
i = minposition;//마지막에 i 갱신 안해줬다.   } }

void insert(int num) { size++; int i= size; hip[size] = num;

while(i != 1) { int pos = i/2;

if(hip[pos]<=hip[i]){
  break;
}

std::swap(hip[i],hip[pos]);
i = pos;

} }

int main() { std::ios_base :: sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

int command; std::cin »command;

for(int i = 0; i< 100000; i++) { hip[i] = 0; } for(int i = 0; i< command; i++){ int temp; std::cin » temp;

if(temp != 0){
  insert(temp);
} else {
  deletemin();
}

} }```

잘못 이해한 힙 성질

• 원소를 제거하고 다운 힘을 할 때는 ‘힙성질을 만족할때 까지’

단순 구현 실수

• 현재 완전 이진트리에 해당하는 부분의 길이를 저장하는 size변수 사용
  0일때 원소 꺼내면 -1되는 것 인덱스 오류 생각못함
  -> 중요한 변수들 범위 벗어나지 않는지 조심.

• 유사하게 현재 탐색중인 노드를 가리키는 i도 갱신안해줬었음.

==> 사용할 변수 선언했다면 각각 신경쓰고 확실히 다 구현해라 (애초에 햇갈일 일없게 줄이고, 명확히 하는 것도 중요한듯.)

이외

• 그냥 다들 stl 이용해서 푼다. priority queue 정도만 알아가도 될듯?.