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

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Heap code in C++
• Buildheap in linear time
• Linear time algorithm
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Programming assignments
• Data structures organize data
• Resource constraints
• Abstract data types
• Tree data structure
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Fundamental data structures
• Computational complexity
• Complexity of algorithms
• Data structure
• Pointers to structures
• Pointers to classes
• Josephus problem
• List data structures
• Doubly linked list
• Circularly linked list
• Code for simulation
• Priority queue
• Tree data structures
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming