tailieunhanh - Lecture Data structures and other objects using C++ - Chapter 11: Heaps

This lecture introduces heaps, which are used in the priority queue project of chapter 11. The lecture includes the algorithms for adding to a heap (including reheapification upward), removing the top of a heap (including reheapification downward), and implementing a heap in a partially-filled array. | Chapter 11 has several programming projects, including a project that uses heaps. This presentation shows you what a heap is, and demonstrates two of the important heap algorithms. Heaps Data Structures and Other Objects Using C++ This lecture introduces heaps, which are used in the Priority Queue project of Chapter 11. The lecture includes the algorithms for adding to a heap (including reheapification upward), removing the top of a heap (including reheapification downward), and implementing a heap in a partially-filled array. Prior to this lecture, the students need a good understanding of complete binary trees. It would also help if they have seen binary search trees and the priority queue class. Heaps A heap is a certain kind of complete binary tree. A heap is a data structure with several applications, including a way to implement Priority Queues, as shown in Chapter 11. The definition of a heap is a special kind of complete binary tree. You probably recall that a complete binary tree requires that its nodes are added in a particular order. Heaps A heap is a certain kind of complete binary tree. When a complete binary tree is built, its first node must be the root. Root The first node of a complete binary tree is always the root. Heaps Complete binary tree. Left child of the root The second node is always the left child of the root. .the second node is always the left child of the root. Heaps Complete binary tree. Right child of the root The third node is always the right child of the root. .then the right child of the root. Heaps Complete binary tree. The next nodes always fill the next level from left-to-right. .and so on. The nodes always fill each level from left-to-right. Heaps Complete binary tree. The next nodes always fill the next level from left-to-right. .from left-to-right. Heaps Complete binary tree. The next nodes always fill the next level from left-to-right. .from left-to-right. Heaps Complete binary tree. The next nodes | Chapter 11 has several programming projects, including a project that uses heaps. This presentation shows you what a heap is, and demonstrates two of the important heap algorithms. Heaps Data Structures and Other Objects Using C++ This lecture introduces heaps, which are used in the Priority Queue project of Chapter 11. The lecture includes the algorithms for adding to a heap (including reheapification upward), removing the top of a heap (including reheapification downward), and implementing a heap in a partially-filled array. Prior to this lecture, the students need a good understanding of complete binary trees. It would also help if they have seen binary search trees and the priority queue class. Heaps A heap is a certain kind of complete binary tree. A heap is a data structure with several applications, including a way to implement Priority Queues, as shown in Chapter 11. The definition of a heap is a special kind of complete binary tree. You probably recall that a complete binary