컴공과고씨

힙은 우선순위 큐를 위해 만들어진 자료구조임. 우선순위큐란 완전이진트리인데 부모가 가지는 값은 자식보다 무조건 큰 값을 가지고 있음.( 혹은 무조건 작은 값). 큰 값을 가지는 것을 최대 힙, 작은 값을 가지는 것을 최소 힙이라고 함. 그래서 루트에는 항상 제일 큰 값 혹은 제일 작은 값을 가지고 있는 것이 특징입니다. 기본적으로 구현 같은 경우 배열을 사용하거나 linked를 사용할 수 있습니다. 저는 배열을 사용하여 구현했습니다. 인덱스 루트 노드의 인덱스를 1로 시작하게 하면 (0번 노드는 버림) 부모 인덱스 = (자식 인덱스) / 2 왼쪽 자식 인덱스 = (부모 인덱스) * 2 오른쪽 자식 인덱스 = (부모 인덱스) * 2 이렇게 나타 낼 수 있겠죠. 위 그림에서 99는 인덱스 1, 50은 2, ..

우선순위 큐는 힙을 이용하여 루트에 우선순위에 따라 최대값 혹은 최소값이 있는 것을 말한다. 선언 struct cmp{ bool operator()(int a, int b){ return a>b; } } #include priority_queue q1; // 루트가 최대인 우선순위 큐 선언 priority_queue; // 루트가 최소값인 우선순위 큐 선언 priority_queue;// 루트가 최소값인 우선순위 큐 선언 자신이 직접 우선순위를 정할 때는 구조체를 생성해주어야한다. 주의 할 것은 벡터는 위와 같이 비교연산을 하면 내림차순으로 정렬된다. 하지만 우선순위 큐는 a가 루트에 있는 값이기 때문에 a가 더 크면 true를 반환한다. 반환값이 true이면 swap를 하겠다는 의미이기 때문에 a와 b..