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; . | Heap code in C template void Heap deleteMin eType amp minItem if isEmpty cout Lecture 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 amp 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 . 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 N h 1. 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 h 2 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 h 1 i h 2 h 1 4 h 2 8 h 3 . 2h 1 1 Multiplying by 2 gives the equation 2S 2h 4 h 1 8 h 2 16 h 3 . 2h 2 Subtract the two equations to get S -h 2 4 8 16 . 2h 1 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
