최소 최대 힙, 트리 관련 알고리즘 강의 필기

힙은 완전 이진트리 자료구조의 일종.
힙에서는 항상 루트노드를 제거하는 방식으로 작동
최소힙 - 루트노드가 가장 작은값
최대힙 - 루트노드가 가장 큰값

원소가들어올때. 최소힙 구성함수, min-heapify
-새로운 데이터가 들어왔을때 heapify 함수가 동작하면 오름차순,내림차순 등으로 힙성질을 유지하도록 유지해줌.
-최악의 경우에도 log n 의 시간복잡도를 가짐

원소가 제거될때 그냥 빈자리에 가장 마지막 자식을 넣으면
자동으로 heapify 가 수행되고, 다시 힙의성질이 만족되는 형태로 구성이된다.
따라서 힙에서 원소를 넣거나뺄때 로그n의 일관적인 시간복잡도를 유지할수있다는 장점.

<트리>
- 가계도같은 계층적 구조를 표현할때 쓰는 자료구조

<이진탐색트리>
-이진탐색이 동작할수 있도록 고안된 효율적인 탐색이 가능한 트리의 일종
왼쪽자식 <부모 <오른족 자식

트리순회
-전위순회 pre-order
-중위순회 in-order
-후위순회 post-order

바이너리 인덱스 트리
-데이터의 변경이 잦고 구간합을 구하라고 할때.
-boj 2042번 문제 참고
-펜윅트리 라고도함(fenwich tree)

정렬(sortring) 알고리즘
-선택정렬(시간복잡도:등차수열 공식에따르면 N제곱): 처리되지 않은 데이터중 가장작은값을 해당범위의 맨앞값과 교환하면서 범위를 좁혀나간다
-삽입정렬 : 앞쪽데이터는 정렬되어있다고 판단하고 , 처리되지 않은 데이터를 하나씩 골라 앞쪽데이터중 적절한위치에 삽입  (시간복잡도 N제곱)
-*많이사용하는* 퀵정렬 : 기준데이터를 설정하고 그 기준보다 큰데이터와 작은 데이터의 위치를 바꾼다
-계수정렬(시간복잡도는 N+K): 값의범위가 명시되어있고 값이 매우많고 그중에  중복값이 많을때 정렬법.(학생성적등등) 데이터범위만큼의 배열을 만들고 해당값이 몇번나왔는지 체크하고 나중에 한꺼번에 출력