완전 이진트리에 있는 노드 중 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
해당 트리의 최소값, 최대값을 보려면 루트 노드만 보면 된다.
- 장점
노드를 추가할 때 해당 위치의 조상 노드하고만 비교하면 된다! (처리 갯수가 줄어든다)
시간 복잡도 : logN
ex) 10억 = 2^30개 일 경우!
일일이 비교할 필요 없이 30번만 비교하면 된다.
- 단점 : 삽입할 때도 logN이지만 삭제할 때도 logN 시간복잡도가 든다.
삭제하려는 노드의 값을 마지막 위치의 노드와 바꾸고 마지막 노드를 삭제한 후 다시 정렬
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드
- 우선순위 큐를 구현하는 가장 효율적인 방법 : 힙
- 우선순위를 가진 항목들을 저장하는 큐
- FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
- int compareTo(T other)
- 음수 : 타 원소가 크다
- 0 : 둘이 같다
- 양수 : 자신이 크다
- int compare(T o1, T o2 )
- 매개변수 두 개를 받아 두 변수를 비교한다.
- 음수 : o2 원소가 크다
- 0 : 둘이 같다.
- 양수 : o1 원소가 크다.
힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행한다.
정렬을 위한 2단계
힙 정렬의 시간 복잡도