CafeM0ca

문제 해결 과정 자료구조 힙을 구현하여 insert와 remove 함수를 작성하여 해결한다. 문제의 제한시간은 1초이다. 따라서 insert 함수와 remove 함수를 O(log N) 시간으로 해결할 수 있도록 구현해야 한다. 시간이 빡빡한 문제이므로 cin.tie와 cin.sync_with_stdio를 꼭 해주자. 그리고 endl 대신 '\n' 으로 개행하자. 구현 #include #include using namespace std; template class max_heap{ public: max_heap(); void insert(type); void remove(int ); void print(); void heapify(int); type operator[](const int); ..

자료구조 heap 특징 merge sort처럼 추가 배열이 필요 없음 complete binary tree에 기반함으로 O(nlogn)의 성능을 보임 heap property max heap property: 부모는 자식보다 크거나 같음 min heap property: 부모는 자식보다 작거나 같음 논리적으로는 배열로 구현가능함 루트 노드: A[1] A[i]의 부모 = A[i/2] A[i]의 왼쪽 자식 = A[i*2] A[i]의 오른쪽 자식 = A[i*2+1] 소스코드 heap.hpp #include #include template class max_heap{ public: max_heap(); void insert(type); void remove(type); int find(type); void so..