Lecture Data Structures: Lesson 32

Chia sẻ: Hàn Thiên Ngạo | Ngày: | Loại File: PPT | Số trang:16

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Data Structures: Lesson 32

Heap 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), or Nh1.
BuildHeap in Linear Time It is easy to see that this tree consists of (20) node at height h, 21 nodes at height h –1, 22 at h2 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 Time The 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 Time Since a complete binary tree has between 2h and 2h+1 nodes S = (2h+1 – 1) (h+1)  N - log2(N+1) Clearly, as N gets larger, the log2(N +1) term becomes insignificant and S becomes a function 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.
Height 1 Nodes Marking the left edges for height 1 nodes
Height 2 Nodes Marking the first left edge and the subsequent right edge for height 2 nodes
Height 3 Nodes Marking the first left edge and the subsequent two right edges for height 3 nodes
Height 4 Nodes Marking the first left edge and the subsequent three right edges for height 4 nodes
Theorem N=31, treeEdges=30, H=4, dottedEdges=4 (H). Darkened Edges = 26 = NH1 (3141)