Lecture Data Structures: Lesson 32

Lecture Data Structures: Lesson 32 provide students with knowledge about heap code in C++; buildheap in linear time; how buildHeap a linear time algorithm; complete binary tree; marking the left edges for height 1 nodes; marking the first left edge and the subsequent right edge for height 2 nodes;...
Nội dung trích xuất từ tài liệu:
Lecture Data Structures: Lesson 32Heap code in C++template void Heap::deleteMin( eType & minItem ){ if( isEmpty( ) ) { cout Lecture No.32 Data Structure Dr. Sohail Aslam Heap code in C++// hole is the index at which the percolate begins.template void Heap::percolateDown( int hole ){ int child; eType tmp = array[ hole ]; for( ; hole * 2 Heap code in C++template const eType& Heap::getMin( ){ if( !isEmpty( ) ) return array[ 1 ];}template void Heap::buildHeap(eType* anArray, int n ){ for(int i = 1; i 0; i-- ) percolateDown( i );} Heap code in C++template bool Heap::isEmpty( ){ return currentSize == 0;}template bool Heap::isFull( ){ return currentSize == capacity;}template int Heap::getSize( ){ return currentSize;} BuildHeap in Linear Time How is buildHeap a linear time algorithm? I.e., better than Nlog2N? We need to show that the sum of heights is a linear function of N(number of nodes).Theorem: For a perfect binary tree of height h containing 2h +1 – 1 nodes, the sum of the heights of nodes is 2h +1 – 1 – (h+1),orNh1. BuildHeap in Linear TimeIt is easy to see that this tree consists of (20)node at height h, 21 nodes at height h –1, 22 ath2 and, in general, 2i nodes at h–i. Complete Binary Tree A h : 20 nodes B C h -1: 21 nodes D E F G h -2: 22 nodes H I J K L M N O h -3: 23 nodes BuildHeap in Linear TimeThe sum of the heights of all the nodes is then S = 2 (h–i), for i= 0 to h1 i = h+2(h1)+4(h2)+8(h3)+…..+2h1(1)Multiplying by 2 gives the equation 2S = 2h+4(h1)+8(h2)+16(h3)+…..+2h(2)Subtract the two equations to get S = -h+2+4+8+16+…..+2h1+2h = (2h+1–1)(h+1)Which proves the theorem. BuildHeap in Linear TimeSince a complete binary tree has between2hand2h+1 nodes S = (2h+1–1)(h+1)  N - log2(N+1)Clearly, as N gets larger, the log2(N +1) termbecomes insignificant and S becomes afunction of N. BuildHeap in Linear Time Another way to prove the theorem. The height of a node in the tree = the number of edges on the longest downward path to a leaf The height of a tree = the height of its root For any node in the tree that has some height h, darken h tree edges – Go down tree by traversing left edge then only right edges There are N – 1 tree edges, and h edges on right path, so number of darkened edges is N – 1 – h, which proves the theorem. Height1NodesMarkingtheleftedgesforheight1nodes Height2NodesMarkingthefirstleftedgeandthesubsequentrightedgeforheight2nodes Height3NodesMarkingthefirstleftedgeandthesubsequenttworightedgesforheight3nodes Height4NodesMarkingthefirstleftedgeandthesubsequentthreerightedgesforheight4nodes TheoremN=31,treeEdges=30,H=4,dottedEdges=4(H).DarkenedEdges=26=NH1(3141)