TAILIEUCHUNG - Lecture Data Structures: Lesson 30

Lecture Data Structures: Lesson 30 provide students with knowledge about inserting into a Heap; finding the minimum is easy; it is at the top of the heap; deleting it (or removing it) causes a hole which needs to be filled; . | Data Structures Lecture 30 Sohail Aslam 1 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 12 15 65 13 14 16 24 21 19 68 65 26 32 31 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 15 7 68 8 9 26 10 32 11 31 12 19 65 13 14 16 24 21 15 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 4 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 DeleteMin Finding the minimum is easy it is at the top of the heap. Deleting it or removing it causes a hole which needs to be filled. 1 13 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 65 6 DeleteMin deleteMin 1 2 14 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 7 DeleteMin deleteMin 1 14 2 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 8 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 8 9 26 10 32 11 31 65 9 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 11 65 10 DeleteMin deleteMin heap size is reduced by 1. 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 65 11 BuildHeap Suppose we are given as input N keys or items and we want to build a heap of the keys. Obviously this can be done with N successive inserts. Each call to insert will either take unit time leaf node or log2N if new key percolates all the way up to the root . 12 BuildHeap The worst time for building a heap of N keys could be Nlog2N. It turns out that we can build a heap in linear time. 13 BuildHeap Suppose we have a method percolateDown p which moves down the key in node p downwards. This is what was happening in deleteMin. 14 BuildHeap Initial data N 15 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7

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