emmaiswatson Developer emmaiswatson Developer

priority queue(우선순위 큐)의 가장 효율적인 구현 방법은 heap 히프 : 여러 개의 값들 중, 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조.완전 이진 트리의 일종. 삽입, 삭제 연산의 복잡도 : O(log(n)) //트리 구조는 높이! logn max heap(최대 히프) : 부모 노드의 키값 >= 자식 노드의 키값 min heap(최소 히프) : 부모 노드의 키값 min heap 사용 -> 삭제연산을 반복하면서 return값들 순서대로내림차순 정렬 -> max heap 사용 -> 삭제 연산을 반복하면서 return값들 순서대로 4. 허프만 코드

1. 선택 정렬(Selection Sort) : O(n^2) 정렬된 리스트 | 정렬되지 않은 리스트 오름차순일 때정렬이 안 된 숫자 중, 가장 작은 수를골라 정렬 안 된 리스트 중 가장 왼 쪽의 원소와 교환하고, 정렬 된 리스트에 포함시킨다.ex.) 5 3 8 1 2 71 ) 3 8 5 2 71 2 ) 8 5 3 71 2 3 ) 5 8 71 2 3 5 ) 8 71 2 3 5 7 ) 81 2 3 5 7 8 ) 2. 삽입 정렬 (Insertion sort) : O(n^2) 정렬된 리스트 | 정렬되지 않은 리스트 오름차순일 때정렬되어있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야하는가를 판단한 후, 해당 위치에 숫자를 삽입.-> 점점 정렬된 리스트의 크기를 키워 나감. ex.) 5 ..