힙 정렬은 병합 정렬, 퀵 정렬만큼 빠른 정렬 알고리즘이다. 힙 정렬은 힙 트리 구조를 이용해서 정렬하는 방법이다. 힙은 완전 이진 트리를 기반으로 하며, 최솟값과 최댓값을 빠르게 찾아낼 수 있다 힙 정렬의 시간 복잡도 계산 1) 주어진 배열을 최대힙 혹은 최소힙으로 만든다 NlgN 2) 삭제를 통해서 정렬을 한다, 루트 노드에 관해서만 heapify를 하면 되기 때문에(이미 루트 빼고는 heapify를 유지하고 있다) lgN이 걸리고 N개를 정렬하는 것이기 때문에 NlgN이 걸린다 두 개의 사건을 독립적이기 때문에 실제 시간 복잡도는 O(NlgN)이라고 할 수 있다

큐는 FIFO 성질을 가진 자료구조다. 즉 먼저 들어간 데이터가 먼저 나오게 된다. 스택 2개를 활용해서 큐를 구현할 수 있다. 스택 하나는 push 용도, 나머지 하나는 pop할 때 이용된다. 만일 pop 명령이 들어온다면 push 때 담긴 스택을 위에서부터 빼서 스택 2번에 넣을 수 있다. 그리고 스택 2에서 위에서부터 pop하면 큐와 똑같이 동작시킬 수 있다

우선순위 큐는 '우선순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용된다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 최대힙은 부모가 자식보다 값이 큰 이진 트리를 의미한다 1. 우선순위 큐의 삽입 1) 배열 맨 끝에 삽입한다 2) 부모와 비교해서 swap을 한다. 가능하다면 루트까지 진행한다 3) 상향식 구조 2. 우선순위 큐의 삭제 1) 0번 인덱스를 추출한다 2) 맨 마지막 원소를 0번으로 넣는다 3) 하향식 구조로 자식들을 비교하면서 0번 인덱스의 기존 위치를 찾는다 #include #define SIZE 1000 typedef struct { int heap[SIZE]; int count; } Pri..

기수 정렬은 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다. 데이터가 총 N개가 있고, 데이터 중 최대 자릿수가 D라고 할 때, 시간복잡도 O(DN)을 가지게 된다. 계수 정렬과 달리 자릿수가 큰 데이터에 대해서도 정렬이 가능하다. 하지만 조금은 느리다는 특징은 있다 단점은 계수 정렬과 마찬가지로 -값이 있을 때는 인덱스를 옮기는 수고를 해야한다

https://noel-embedded.tistory.com/495 기존 priority_queue STL 세번째 인자인 class Compare = std::less 함수를 만들기 위해서 cmp 클래스를 만들고, 그 안에 연산자를 만들어서 오버로딩을 했다. 이는 다양한 연산자 오버로딩을 구분할 수 있어서 좋다 하지만 하나의 연산자만 구현한다면 클래스 없이