Heap 자료구조 +
Heap 정렬
신찬수
정렬
• 입력 숫자 (또는 문자열)을 크기에 따라 내림차순 또는 오름차순으로 나열하는 것.
• Example: 7 9 6 2 10 4 5 9 8
–
오름차순 정렬: 2 4 5 6 7 8 9 9 10–
내림차순 정렬: 10 9 9 8 7 6 5 4 2• 여러 응용분야 사용되는 매우 기본적인 알고리즘.
• 기본 정렬 알고리즘
–
Insertion sort, selection sort, bubble sort, etc.• 고급 정렬 알고리즘
–
Quick sort, merge sort, heap sort, radix sort etc.Bubble sort
•
Example: 7 9 6 2 10 4 5 8•
Time:for i = 0 to n – 1
for j = n – 1 to i + 1
if ( A[j – 1] > A[j] )
Swap A[j – 1] and A[j];
Selection sort
•
Example: 7 9 6 2 10 4 5 8•
Time:for (j = n-1; j > 0; j--) {
k = FindMaximum(A[0]~A[j]) Swap A[j] and A[k]
}
Bubble/Insertion 정렬 알고리즘
• 수행시간: O(n
2)
• 장점
–
이해하기 쉽다.–
코딩하기 쉽다.–
입력 숫자가 적은 경우엔 매우 빠르다.• 단점
–
입력 숫자가 많아지면 매우 느려진다.빠른 정렬 알고리즘: Heap 정렬
• Heap 자료구조를 이용한 heap 정렬
• 수행시간: O(n log n)
–
최적 수행 시간임Heap 자료구조
•
Heap은 배열에 저장된 이진 트리이며, 다음의 힙 성질 을 만족한다.– 트리의 마지막 레벨을 제외하곤 모든 레벨에 노드가 빠짐없이 존재해야 하며, 마지막 레벨엔 왼쪽부터 노드가 채워져 있어야 한다.
– 각 노드에 저장된 값은 자신의 자손 노드에 저장된 값보다 절대 작지 않다.
15
11
6
1
12
2 3
8
10
15 12 6 11 10 2 3 1 8
부모노드, 자식노드 자손노드, 루투노드
트리 높이
연습
9
2
15
7 1
3
10
3 10 2 4 7 9 1 21 15 9 31 17
9 21 31
17
4
Heap 구성: make_heap
•
어떤 노드가 A[k]에 저장되어 있다면, A[k]의 왼쪽과 오른쪽 자식 노드는 어디에 저장되어 있나?•
A[k]의 부모 노드는 어디에 저장되어 있나?15
11
6
1
12
2 3
8
10
15 12 6 11 10 2 3 1 8
A
Heap 구성: 계속
1.
입력 숫자를 재 배치해서 heap을 구성한다.2
1
6
12
8
15 3
11
10
2 8 6 1 10 15 3 12 11
A
2
12
6
1
8
15 3
11
10
A 2 8 6 12 10 15 3 1 11
Heap 구성: 계속
1.
입력 숫자를 재 배치해서 heap을 구성한다.2
12
6
1
8
15 3
11
10
2 8 6 12 10 15 3 1 11
A
2
12
15
1
8
6 3
11
10
A 2 8 15 12 10 6 3 1 11
Heap 구성: 계속
1.
입력 숫자를 재 배치해서 heap을 구성한다.2
8
15
1
12
6 3
11
10
2 12 15 8 10 6 3 1 11
A
2
11
15
1
12
6 3
8
10
A 2 12 15 11 10 6 3 1 8
Heap 구성: 계속
1.
입력 숫자를 재 배치해서 heap을 구성한다.15
8
2
1
12
6 3
11
10
15 12 2 8 10 6 3 1 11
A
15
11
6
1
12
2 3
8
10
A 15 12 6 11 10 2 3 1 8
Heap 구성: 계속
•
make_heap 함수의 수행시간은? _________________– n개의 숫자를 저장한 heap의 높이는?
– 1번 단계에서 힙을 구성할 때, 하나의 숫자를 재배치하는 데 움직인 높이는 최대 얼마인가?
11
8
6
1
12
2 3
15
10
연습
3 10 2 4 7 9 1 21 15 9 31 17
Heap 정렬:
2.
루트 노드 A[0]와 마지막 노드 A[n-1]을 교환한다.• 교환 후 새로운 루트 노드의 값을 힙 성질이 만족하도록 재 배치.
15
11
6
1
12
2 3
8
10
A 15 12 6 11 10 2 3 1 8
8
11
6
1
12
2 3
15
10
A 8 12 6 11 10 2 3 1 15
Heap 정렬: 계속
2.
루트 노드 A[0]와 마지막 노드 A[n-1]을 교환한다.• 교환 후 새로운 루트 노드의 값을 힙 성질이 만족하도록 재 배치.
12
8
6
1
11
2 3
15
10
A 12 11 6 8 10 2 3 1 15
1
8
6
12
11
2 3
15
10
A 1 11 6 8 10 2 3 12 15
Heap 정렬: 계속
2.
루트 노드 A[0]와 마지막 노드 A[n-1]을 교환한다.• 교환 후 새로운 루트 노드의 값을 힙 성질이 만족하도록 재 배치.
1
6
3
12
2
10 11
15
8
A 1 2 3 6 8 10 11 12 15
Heap Sort의 수행시간
•
2번 단계에서 루트 노드와 가장 마지막 노드를 교환한 후, 새로운 루트 노드의 값이 재배치되는 데 움직인 높이는 최대 얼마인가?•
따라서, 하나의 숫자가 재배치하는 데 걸리는 최대 시간은•
전체 시간은다른 연산
•
heap에 새로운 값 x를 삽입하고 싶다면?– void insert( int A[ ], int n, int x )
– 현재 heap A에 n개의 노드가 있다고 가정하자.
– A[n] = x를 저장한다.
– x의 위치가 heap에서의 자기 위치가 아닐 수 있다.
– 이 경우에는 어떻게 x를 제 자리로 보낼 수 있을까?
정렬을 이용한 문제 (강의숙제1)
•
입력– k
key 값 (100,000보다 작은 양의 정수)
– n개의 100,000보다 작은 양의 정수
n개의 정수는 모두 다르다고 가정.
•
출력– n개의 정수 중 두 정수의 합이 k가 되는 모든 정수 쌍을 찾아 출력하라.
•
예– k = 16, n = 8
– 10, 14, 2, 8, 7, 9, 1, 6 – 답: (10, 6), (14, 2), (7, 9)
입력(input.txt)과 출력
2 테스트 데이터의 개수 16 첫번째 데이터에서의 k 8 n
10 14 2 8 7 9 1 6 n개의 양의 정수 7 두번째 데이터에서의 k
5 n
4 3 1 2 6 5개의 양의 정수
(10, 6) (14, 2) (7, 9) (4, 3) (1, 6)
