어제의 나보다 성장한 오늘의 나

Priortity Queue와 Pair를 함께 사용하면 어떤 기능을 할 수 있는지 알아보자. ① 기본적인 사용 첫 번째 인자 기준으로 내림차순 정렬, 같다면 두 번째 인자를 기준으로 내림차순 정렬. priority_queue pq; pq.push({1,2}); pq.push({1,3}); pq.push({2,2}); pq.push({2,5}); pq.push({3,1}); while(!pq.empty()){ cout

Heap 이란? ◎ complete binary tree (parent node는 2개의 child node를 갖는다.) ◎ parent 와 child 간에 항상 대소 관계가 성립 ◎ parent node가 child node 보다 항상 크면 max heap, 항상 작으면 min heap ◎ max heap일때는 최상위 node가 가장 크고 , min heap일때는 최상위 node가 가장 작다. ◎ array의 index는 1 부터 사용한다. ◎ child index는 (parent_index)*2 , (parent_index)*2+1 ◎ 반대로 parent index는 (child_index) / 2 1. heap 구현 Array를 이용하여 Maxheap을 구현해보았다. 변수 / 생성자 / 소멸자 pr..