일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- java
- 2P1L
- 딥러닝
- 벡터해석
- dictionary
- Python
- 강화학습
- auto-encoder
- 파이썬
- 델
- 미분 방정식
- 소행성
- 선적분
- 피보나치 수열
- 회로이론
- 최단 경로
- 백트래킹
- 코드업
- BST
- 자료형
- cURL
- 벡터 해석
- 딕셔너리
- 이진탐색트리
- 계단 오르기
- 함수
- Class
- 자바
- Asteroid RL
- 신경망
- Today
- Total
Zeta Oph's Study
[Data Structure (Java)] Heapsort 본문
https://crane206265.tistory.com/85
[Data Structure (Java)] Heap
https://crane206265.tistory.com/84 [Data Structure (Java)] Tree (3) - Binary Search Treehttps://crane206265.tistory.com/82 [Data Structure (Java)] Tree (2) - Tree Traversal Algorithmshttps://crane206265.tistory.com/81 [Data Structure (Java)] Tree (1) -
crane206265.tistory.com
저번에 Heap을 공부했으니까, 이번엔 Heapsort를 공부해봅시다.
Heapsort Algorithm
1. heap construction : create a max-heap with all N keys
2. sortdown : repeatedly remove the maximum key
1. Heap Construction
Original array : Heap that violating heap-order
Every position in the array is the root of small subheap
--> Call sink() on all nodes make the subtree rooted at this node a heap
* Start scanning at halfway back through the array : Skip the subheaps of size 1
--> Finish calling sink() at the root (index 1)
==> The array restored to satisfy heap-order
// heap construction code
for(int k = N/2; k >= 1; k--) //N/2 : start scanning at halfway back
sink(a, k, N) //a : target array & N : heap size
2. Sortdown
(1) Exchange the largest one with the last position in the array
(2) Remove the last one(the largest one) from the heap - (it is sorted : do not touch)
(3) Call sink() at the root : Restored heap to satisfy heap-order
(4) Repeat (1)~(3) until the heap becomes empty
==> All elements are sorted
while(N>1) {
exch(a, 1, N--);
sink(a, 1, N);
}
Running Time Analysis
1. sink-based heap construction : O(n)
<worst case>
at the root : exchange $h$ times
at the next level : $2(h-1)$ times <- (2 trees of height h-1)
at the next level : $4(h-1)$ times
...
at the bottom : no exchange
--> $\text{total exchange} = h+2(h-1)+4(h-2)+...$
$=2^{h+1}-h-2=(2^{h+1}-1)-h-1$
$=n-(h+1)<=n$
2. sortdown : O(n log n)
sink() -> exchange at most log n times
sink() for n keys
==> Heapsort : In-place sorthing algorithm with O(n log n)
* In-place : Instead of transferring elements out of the sequence and then back in, we simply rearrange them
--> useful at tight memory
Heapsort Implementation
Heapsort Implementation as method in Heap class (for String)
import java.lang.Comparable;
public class Heap {
//This class cannot be instantiated : just for sorting
private Heap() {}
//----- Heapsort -----
@SuppressWarnings("rawtypes")
public static void sort(Comparable[] pq) {
int n = pq.length;
for(int k = n/2; k >= 1; k--) {
sink(pq, k, n);
}
while(n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}
//----- helper methods -----
@SuppressWarnings("rawtypes")
private static void sink(Comparable[] pq, int k, int n) {
while(2*k <= n) {
int j = 2*k;
if(j < n && less(pq, j, j+1)) j++;
if(!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
//Heap is 1-based indexing, but given array starts at index 0
//==> implement less(), exch() method with considering this
@SuppressWarnings({ "rawtypes", "unchecked" })
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i-1].compareTo(pq[j-1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object temp = pq[i-1];
pq[i-1] = pq[j-1];
pq[j-1] = temp;
}
}
'프로그래밍 > Java' 카테고리의 다른 글
[Data Structure (Java)] Hash (Separate Chaining & Linear Probing) (1) | 2024.06.05 |
---|---|
[Data Structure (Java)] Map (1) | 2024.06.03 |
[Data Structure (Java)] Heap (2) | 2024.06.02 |
[Data Structure (Java)] Tree (3) - Binary Search Tree (1) | 2024.06.01 |
[Data Structure (Java)] Tree (2) - Tree Traversal Algorithms (1) | 2024.05.13 |