[Data Structure] 히프 정렬 - Heap Sort

히프 정렬 (Heap Sort) Unstable Sort 완전이진트리 구조 배열을 이용해서 구현 or 컬렉션을 통해서 구현 시간복잡도 - O(n log n) 장점 - 추가 메모리가 필요없고 항상 O(n log n)의 시간복잡도를 가진다 단점 - 보통의 경우, 퀵정렬보다 느리다 데이터의 상태에 따라서 다른 정렬들에 비해 조금 느리다 - 안정성을 보장받지 못한다 과정 - 최대힙 : 힙에서 pop시킨 요소를 배열의 뒤에서부터 채운다 - 최소힙 : 힙에서 pop시킨 요소를 배열의 앞에서부터 채운다 C : 직접 구현 Java : PriorityQueue / 직접 구현 Python : heapq / PriorityQueue / 직접 구현 ▶ PriorityQueue 이용 PriorityQueue pq1 = new ..

2022.01.01