힙정렬
1. 최악의 경우 시간복잡도 : O(nlog2n)
2. sorts in place : 추가 배열 불필요 [공간 복잡도 이득]
3. 이진 힙 자료구조 이용
힙의 정의
힙 : 완전이진트리이면서 힙 속성 만족
[힙은 동일 데이터를 가진 서로 다른 힙이 존재 가능하며, 유일하지 않다]
[최대 힙 : 부모는 자식보다 크거나 같다.]
[최소 힙 : 부모는 자식보다 작거나 같다.]
전이진 트리 : 모든 레벨에 노드들이 꽉 차있는 형태
완전이진트리 : 마지막 레벨 제외하면 완전히 차있고, 마지막 레벨에 가장 오른쪽부터 연속된 노드가 비어있을수있음
힙의 표현
1. 일차원 배열로 표현 : A[1...n]
2. 루트 노드 : A[1]
3. A[i]의 부모 : A[i/2]
4. A[i]의 왼쪽 자식 : A[2i]
4. A[i]의 오른쪽 자식 : A[2i+1]
전체를 힙으로 : MAX-HEAPIFY
-> 트리 전체 모양은 완전 이진 트리
[두 자식들 중 더 큰쪽이 자신보다 크면 교환]
루트만 힙 속성 만족안함
-> 왼쪽 부트리와 오른쪽 부트리가 그 자체로 힙인 경우
//1. MAX-HEAPIFY - recursive
MAX-HEAPIFY(A, i)
//노드i가 루트 노드인 서브트리를 heapify
//루트 노드에 대한 heapify : MAX-HEAPIFY(1)
{
if there is no child of A[i]
return;
k <- index of the biggest child of i;
if A[i] >= A[k]
return;
exchange A[i] and A[k];
MAX-HEAPIFY (A,k);
};
//2. MAX-HEAPIFY - iterative
MAX-HEAPIFY(A, i)
{
where A[i] has a child do
k <- index of the biggest child of i;
if A[i] >= A[k]
return;
exchange A[i] and A[k];
i=k;
end.
}
힙 정렬
1. 주어진 데이터로 힙을 만든다.
2. 힙에서 최대값(루트)를 가장 마지막 값과 바꾼다.
3. 힙의 크기가 1 줄어든 것으로 간주한다. [가장 마지막 값은 힙의 일부가 아닌 것으로 간주]
4. 루트노드에 대해서 HEAPIFY(1)한다.
5. 반복
// 힙 정렬 시간 복잡도
HEAPSORT(A)
BUILD-MAX-HEAP(A) : O(n)
for i <- heap_size downto 2 do : n-1 times
exchange A[1] <-> A[i] : n-1 times
heap_size <- heap_size -1 : O(1)
MAX-HEAPIFY(A,1) : O(log2n)
-> O(nlog2n)
우선순위 큐
1. 최대 우선순위 큐
: INSERT(x) - 새로운 원소 x를 삽입
: EXTRACT_MAX() : 최대값을 삭제하고 반환
2. 최소 우선순위 큐
: INSERT(x) - 새로운 원소 x를 삽입
: EXTRACT_MIN : 최소값을 삭제하고 반환
MAX-HEAP-INSERT (A, key) {
heap_size = heap_size+1;
A[heap_size] = key;
i = heap_size;
while (i>1 and A[PARENT(i)] < A[I]) {
exchange A[i] and A[PARENT(i)];
i = PARENT(i);
}
}
EXTRACT-MAX(A) {
if heap-size[A] <1
then error "healp underflow"
max <- A[1]
A[1] <- A[heap-size[A]]
heap-size[A] <- heap-size[A] -1
MAX-HEAPIFY (A,1)
return max;
}
'Java > Java 알고리즘' 카테고리의 다른 글
[알고리즘] 3-5. 자바의 정렬 (0) | 2022.03.02 |
---|---|
[알고리즘] 3-4. 분할 정복을 이용한 정렬 (3) (0) | 2022.03.02 |
[알고리즘] 3-2. 분할 정복을 이용한 정렬 (0) | 2022.03.02 |
[알고리즘] 3-1. 기본 정렬 (0) | 2022.03.02 |
[알고리즘] 2-2. 순열 (0) | 2022.03.02 |