20162317 2017-2018-1 《程式設計與資料結構》第9周學習總結 18章 堆
教材學習内容總結
1、 堆的引入
.
2、堆的用處
1.實作優先隊列
2.總能友善地得到元素集合中的最大（小）值（最大（小）值在根部)
3.能夠用來進行排序
3、堆的概念與性質
4、 堆的實作
教材學習中的問題和解決過程
- 問題1：我在課本中看到這麼一句話：“堆是一棵完全二叉樹，其中每個元素都要大于或小于它的所有孩子”但下面的關鍵概念中也寫着：“堆是一棵完全二叉樹，其中每個元素大于等于其所有子結點的值”那每個元素是大于或小于其所有子結點還是大于等于其所有子結點？？
- 問題1解決方案：翻閱書後面的自測題SR18.1的答案，上面寫着：“堆中的結點大于等于它的兩個子結點”。
是以可以得出結論，應該是每個元素大于或等于其所有子結點的值。
補充：實際上，上面我得到的結論是最大堆的結論，最小堆的性質是：每個元素都小于等于它的孩子，也就說明了小于也是正确的。
- 問題2：我在書中看到這麼一句話：“堆是一種經典的是資料結構，常用來實作優先隊列”，什麼是優先隊列，它與隊列是否不同，若不同，不同處在哪裡？？
- 問題2解決方案：在書的後面有對優先隊列進行解釋：
- 具有更高優先級的項排在前面
- 具有相同優先級的項按先進先出的規則排序
- ...
代碼調試中的問題和解決過程
- 問題1：在單步跟蹤LinkedMaxHeap的過程中，有個add方法：
@Override
public void add(T element) {
HeapNode<T> node = new HeapNode<T>(element);
HeapNode<T> newParent = null;
if (root == null) {
root = node;
} else {
newParent = ((HeapNode<T>) root).getParentAdd(last);
if (newParent.getLeft() == null) {
newParent.setLeft(node);
} else {
newParent.setRight(node);
}
}
node.setParent(newParent);
last = node;
((HeapNode<T>) root).heapifyAdd(last);
}
其中有段代碼：
node.setParent(newParent);
在add方法中已經明确表明
newParent.setLeft(node);
那設定node結點的父節點是newParent有什麼意義？
- 問題1解決方案：解決這個問題要結合HeapNode的代碼。在HeapNode的代碼中有個HeapNode的變量parent，在裡面的很多方法裡面，都有用到這個變量，書上也有說：“有到父節點的引用，這樣就可以沿樹中的路徑移動。”是以setParent方法是在堆中必要的
- 問題2：在看HeapNode中的heapifyAdd方法的時候，看到這麼一句代碼：
current = current.parent;
current都成為它自己的父節點了，那子結點還在嗎？
- 問題2解決方案：在！current隻是目前結點的其中一個引用罷了，上面那段代碼隻是引用改變了而已，堆還是原來的樣子。
代碼托管
上周考試錯題總結
- 錯題1：在一棵二叉查找樹中，左子樹的元素________根的元素
A.大于
B.小于
C.大于或等于
D.小于或等于
E.等于
我的答案：B 标準答案：D
解析：當出現元素重複的情況，一個元素會作根，另一個相同的元素會作根的左子結點或右子結點
學習進度條
| | 代碼行數（新增/累積）| 部落格量（新增/累積）|學習時間（新增/累積）
| -------- | :----------------😐:----------------😐:---------------: |:-----😐
| 目标 | 5000行 | 15篇 | 400小時 | |
| 第一周 | 200/200 | 2/2 | 20/20 | |
| 第二周 | 20/220 | 1/3 | 20/40
| 第三周 | 645/865 | 1/4 | 14/54 | |
| 第五周 | 654/1519 | 1/5 | 18/72
| 第六周 | 436/1955 | 1/6 | 16/88 | |
| 第七周 | 839/2794 | 2/8 | 20/108 |
| 第八周 | 2143/4937 | 2/10 | 25/133 |
| 第九周 | 1368/6305 | 2/12 | 18/151 ||
- 計劃學習時間:16小時
- 實際學習時間:18小時