20162314 2017-2018-1 《Program Design & Data Structures》Learning Summary Of The Ninth Week
Summary of Key Concepts
A heap is a complete binary tree in which each element is greater than or equal to both of its children.
Adding an element to a heap can be accomplished by adding the element as a leaf, then moving it upward as appropriate.
Removing the maximum element from the heap can be accomplished by replacing the root with the last leaf, then moving it downward as appropriate.
A heap sort makes use of the primary characteristic of a heap to sort a set of elements.
A priority queue is not a FIFO queue. It orders elements according to priority,independent of the order in which they are added to the queue.
Problem and solution in teaching materials.
What is the difference between a heap and a binary search tree?
- A binary search tree and a heap are both binary trees that have constraints on the relationships among their elements. The nodes in a binary search tree are less than their left child and
- greater than or equal to their right child, whereas the nodes in a heap (maxheap) are greater than or equal to both children.
What is the difference between a minheap and a maxheap?
- A minheap keeps the smallest value in the tree at the root,whereas a maxheap keeps the largest value at the root.
- Otherwise, their strategies and implementations are similar.
How is the largest element removed from a heap?
- The maximum element is removed from a heap (maxheap) by replacing the root with the last leaf of the tree, then moving that
- element down the tree as appropriate to reassert the proper relationships among the elements.
Code hosting
Summary of error for last week.
Linear search is always more effective than binary search.The answer should be false, for the situation of "n = 2".
Evaluate for my partner
- Advantage and problem in the blog：
- Concise and comprehensie
- Uncleary to the content
- Mould is amazing
- Advantage and problem in the code：
- Serious writing.
- Wonderful idea
- Too less
Learning situation of partner
- Learning content of partner：
- Algorithm
- Recursion
- HanoiTowers and maze
Anything else that want to say
- It's not easy to persere on utizing English to write a blog.But I'm getting used to doing this because of the benefit.
Academic progress check
| Code line number（increasing/accumulative） | Blog number（inc/acc） | studying time（inc/acc） | progress | |
|---|---|---|---|---|
| target | 5000lines | 30articles | 400hours | |
| First week | 180/180 | 1/1 | 20/20 | |
| Second week | 1049/1229 | 1/2 | 18/38 | |
| Third week | 1037/2266 | 3/7 | 22/60 | |
| Fourth week | 1120/3386 | 2/9 | 30/90 |