힙

힙은 우선순위큐를 구현하기 가장 적합한 자료구조이다.

이진트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.

우선순위 큐: FIFO 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐(자료구조가 아닌 개념이다!)
우선순위큐≠ 힙

특징

• 우선순위가 높은 요소가 먼저 나가는 특징
• 루트가 가장 큰값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이있다.
• 최대, 최소를 찾을 때는 O(1) 시간 복잡도를 가진다
• 자바스크립트는 힙을 직접 구현해야된다.

힙 추가 알고리즘

• 요소가 추가될 때 트리의 가장 마지막 정점에 위치한다.
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 완전 이진트리의 높이는 log N 이기에 힙의 요초 추가 알고리즘은 O(log N) 시간 복잡도를 가진다.

힙 요소 제거 알고리즘

• 요소제거는 루트 정점만 가능
• 루트정점이 제거된 후 가장 마지막 정점이 루트에 위치
• 루트 정점의 두자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때 까지 반복한다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(log N) 시간 복잡도를 가진다.

정렬

요소들을 일정한 순서대로 열거하는 알고리즘

특징

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재

비교식 정렬

• 버블 정렬: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘, O(n^2) 시간복잡도를 가진다.
• 선택 정렬: 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 알고리즘 O(n^2) 시간복잡도를 가진다.
• 삽입정렬: 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 알고리즘 O(n^2) 시간복잡도를 가진다.

분산식 정렬

• 분할 정복: 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략
• 합병 정렬: 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘 O(n log n) 시간복잡도
• 퀵 정렬: 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬 O(n log n) 시간복잡도

JS sort Method

아스키 형식으로 정렬 되기때문에 주의해야됨

선형 탐색

순서대로 하나씩 찾는 탐색 알고리즘 O(n) 시간복잡도

이진 탐색

졍렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘 O(n log n)

특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(n log n) 시간복잡도인 만큼 상당히 빠르다.

이진 탐색 트리

이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고, 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진탐색트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있으며, 순차 탐색과 동일한 시간복잡도를 가지게 된다.
• 이를 해결하기 위해 AVL트리, 레드-블랙 트리와 같은 자료구조를 이용하여 이진 탐색 트리의 균형을 맞출 수 있다.

🚑깨달은 점

힙을 우선순위 큐라고 동일 시 여겼는데 이번 자료구조 알고리즘을 공부하면서 다르게 생각하게 되었다. 정확히 말하면 자료구조와 알고리즘을 구분할 수 있게 된거같다! 또한 정렬을 학습했을 때 분류없이 학습을 했지만 이번에 비교식, 분산식으로 학습을 하니 정렬의 특징을 더 이해할 수 있게 되었다.

그리고 깨알팁은 JS sort메서드가 아스키 형식으로 정렬된다는 것을 알았다. (놓치고 있었던 부분)🚨

하루에 많은 양의 학습을 하지만 그래도 이렇게 TIL을 적으면서 나중에 다시 나의 글을 읽었을 때 기억 날 수 있도록 꾸준히 글을 써야겠다. 생각이 들었다. 벌써 5일차 지만 많은 것을 배워서 뿌듯? 걱정?이다!!😎