11강-힙정렬.ppt

Size: px

Start display at page:

Download "11강-힙정렬.ppt"

승현 오
4 years ago
Views:

1 11 (Heap ort)

2 Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort

3 11.1 (Priority Queue) Operations

4 ? Priority Queue? Priority Queue tack Push : Pop : Queue Put : Get : Heap Insert : emove :

5 Operations (Construct) N (Insert) (emove) (eplace) (Change) (Delete) (Join)

6 11.2 (Heap)? Insert Operation emove Operation

7 Heap? Full Binary Tree.! oot T M G OTALGOIM O O A I L

8 Insert Operation, UpHeap T T M G Z G O O A I L Z O O A I L M T Z Z T G G O O A I L M O O A I L M

9 emove Operation oot, oot, DownHeap T Z M T G G O O A I L M O O A I L T T M G M G O O A I L O O A I L

10 11.3 UpHeap/Insert DownHeap/Extract

11 Level-Order Traversal 1? Full Binary Tree Index Node T M G O O A I L O O A I T L M G

12 . Index Node A L G O L A G O

13 Child/Parent j j/2. j j*2, j*2+1. N (N/2). O O A I T L M G

14 UpHeap/Insert Operation O O A I T M L Z 13 G void UpHeap(TYPE a[], int k) { TYPE v; v = a[k]; while (a[k/2] < v && k > 1) } { //. a[k] = a[k/2]; k /= 2; } a[k] = v; void Insert(TYPE a[], int& n, TYPE v) { a[++n] = v; // UpHeap(a, n); // UpHeap }

15 DownHeap/Extract Operation T O O A I L M Z G void DownHeap(TYPE a[], int n, int k) { int i; TYPE v = a[k]; while (k <= n/2) // { i = k * 2; // i k Left Child if (i < n && a[i] < a[i+1]) i++; // if (v >= a[i]) break; // a[k] = a[i]; // k = i; } a[k] = v; // k v } TYPE Extract(TYPE a[], int& n) { TYPE v = a[1]; // root = a[1] = a[n--]; // root DownHeap(a, n, 1); // root DownHeap return v; }

16 11.4 (Heap ort) class Heap

17 (Construct). ( ) Extract. void Heaport(TYPE a[], int n) { int i; int len = 0; // for (i = 1; i <= n; i++) // Insert(a, len, a[i]); for (i = len; i >= 1; i--) // a[i] = Extract(a, len); }

18 class Heap template <class TYPE> class Heap { public: Heap(); Heap(TYPE a[], int n); void etarray(type a[], int n); TYPE& a(int k) { return m_parray[k-1]; } int GetHeapLen() { return m_nheaplen; } void etheaplen(int n) { m_nheaplen = n; } void UpHeap(int k); void DownHeap(int k); void Insert(TYPE v); TYPE Extract(void); private: TYPE *m_parray; int m_narraylen; int m_nheaplen; }; a[k] a(k) > ==.

19 class Heap Implementation template <class TYPE> void Heap<TYPE>::UpHeap(int k) { TYPE v; v = a(k); while (v > a(k/2) && k > 1) { a(k) = a(k/2); k /= 2; } a(k) = v; } template <class TYPE> void Heap<TYPE>::Insert(TYPE v) { a(++m_nheaplen) = v; UpHeap(m_nHeapLen); } template <class TYPE> void Heap<TYPE>::DownHeap(int k) { int i; TYPE v; v = a(k); while (k <= m_nheaplen/2) { i = k*2; // Left-Child if (i < m_nheaplen && a(i+1) > a(i)) i++; if (v > a(i) v == a(i)) break; a(k) = a(i); k = i; } a(k) = v; } template <class TYPE> TYPE Heap<TYPE>::Extract(void) { TYPE v = a(1); a(1) = a(m_nheaplen--); DownHeap(1); return v;

20 Heaport Function template <class TYPE> void Heaport(TYPE a[], int n) { int i; Heap<TYPE> heap(a, n); for (i = 1; i <= n; i++) heap.insert(heap.a(i)); while (n > 1) heap.a(n--) = heap.extract(); } Extract

21 11.5

22 Extraction.

23 d = log 2 N + 1 N Insert, Extract, DownHeap, UpHeap O(logN). Full Binary Tree: N logn+1 Heaport O(NlogN) : N Insert O(NlogN) : N Extract O(NlogN)!!

24 11.6

25 Bottom-Up Heap Creation? Heap DownHeap Full Binary Tree N/2 Leaf Node DownHeap. Top-Down T TOOTALGOITHM O O T A L G O I T H M

26 template <class TYPE> void Heaport_up(TYPE a[], int n) { int k; Heap<TYPE> heap(a, n); // heap.etheaplen(n); } // DownHeap // Bottom-Up Heap Creation for (k = n/2; k >= 1; k--) heap.downheap(k); while (n > 1) heap.a(n--) = heap.extract(); Top-Down Creation N Insert Bottom-Up Creation N/2 DownHeap Animation :

27 11.7 andom Array orted Array everse Array

28 andom Array andom Array Heaport Heaport_up

29 orted Array orted Array Heaport Heaport_up orted Array Top-Down Bottom-Up? orted Array

30 everse Array everse Array Heaport Heaport_up Bottom Up Heaport_up.

31 11.

32 11 Heap, Full Binary Tree Binary Tree k k/2, k k*2, k*2+1. Heap ort Heap Creation Heap Extraction. Top-Down Creation vs Bottom-Up Creation O(NlogN),.

6장정렬알고리즘.key

6장정렬알고리즘.key 6 : :. (Internal sort) (External sort) (main memory). :,,.. 6.1 (Bubbble Sort).,,. 1 (pass). 1 pass, 1. (, ), 90 (, ). 2 40-50 50-90, 50 10. 50 90. 40 50 10 비교 40 50 10 비교 40 50 10 40 10 50 40 10 50 90