TAILIEUCHUNG - Lecture Data Structures: Lesson 31

Lecture Data Structures: Lesson 31 provide students with knowledge about buildheap; the general algorithm is to place the N keys in an array and consider it to be an unordered binary tree; the following algorithm will build a heap out of N keys; . | BuildHeap The general algorithm is to place the N keys in an array and consider it to be an unordered binary tree. The following algorithm will build a heap out of N keys. for i N 2 i gt 0 i- percolateDown i BuildHeap 1 Why I n 2 i 15 2 7 65 2 31 3 32 4 26 5 21 6 19 7 68 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 12 13 i 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 15 2 7 65 2 31 3 32 4 26 5 21 6 19 7 12 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 6 65 2 31 3 32 4 26 5 21 6 19 i 7 12 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 5 65 2 31 3 32 4 26 5 21 i 6 5 7 12 8 9 24 10 15 11 14 12 16 13 19 14 70 15 68 13 i 65 31 32 26 21 5 12 13 24 15 14 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 4 65 2 31 3 32 4 26 i 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 13 i 65 31 32 26 14 5 12 13 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 3 65 2 31 3 32 i 4 13 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 26 i 65 31 32 13 14 5 12 26 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 2 65 2 31 i 3 5 4 13 5 14 6 16 7 12 8 9 24 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 31 5 13 14 16 12 26 24 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i i 1 65 2 13 3 5 4 24 5 14 6 16 7 12 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 13 5 24 14 16 12 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 Min heap 5 2 13 3 12 4 24 5 14 6 16 7 65 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 5 13 12 24 14 16 65 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Other Heap Operations decreaseKey p delta lowers the value of the key at position p by the amount delta . Since this might violate the heap order the

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Build Heap
• Unordered binary tree
• Heap operations
• 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