11 (Heap ort) leejaku@shinbiro.com
Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort
11.1 (Priority Queue) Operations
? Priority Queue? Priority Queue tack Push : Pop : Queue Put : Get : Heap Insert : emove :
Operations (Construct) N (Insert) (emove) (eplace) (Change) (Delete) (Join)
11.2 (Heap)? Insert Operation emove Operation
Heap? Full Binary Tree.! oot T M G OTALGOIM O O A I L
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
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
11.3 UpHeap/Insert DownHeap/Extract
Level-Order Traversal 1? Full Binary Tree Index 1 2 3 4 5 6 7 8 9 10 11 12 Node T M G O O A I L O O A I T 2 3 1 L M 4 5 6 7 8 9 10 11 12 G
. Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Node A L G - - - O - - - - - - - L A 2 3 1 G 4 5 6 7 O 8 9 10 11 12 13 14 15
Child/Parent j j/2. j j*2, j*2+1. N (N/2). O O A I T 2 3 1 L M 4 5 6 7 8 9 10 11 12 G
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 }
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; }
11.4 (Heap ort) class Heap
(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); }
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; }; 1. 0. a[k] a(k) > ==.
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;
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
11.5
Extraction.
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)!!
11.6
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
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 : http://ciips.ee.uwa.edu.au/~morris/year2/pld210/heapsort.html
11.7 andom Array orted Array everse Array
andom Array andom Array Heaport Heaport_up
orted Array orted Array Heaport Heaport_up 8 6 19 14 42 31 92 67 199 144 430 310 orted Array Top-Down Bottom-Up? orted Array
everse Array everse Array Heaport Heaport_up 7 6 14 13 30 28 65 61 142 133 305 289 Bottom Up Heaport_up.
11.
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),.