《算法導論(第4版)》閱讀筆記:p162-p163
《算法導論(第4版)》學習第 28 天,p162-p163 總結,總計 2 頁。
一、技術總結
1. heap sort
(1) (binary) heap(堆/二叉堆)
(2)complete binary tree(完全二叉樹)
(3)max-heap(最大堆)
定義:A[PARENT(i)] ≥ A[i]。
看了很多定義,不得不說還是這個定義最簡潔,準確。
(4)min-heap(最小堆)
定義:A[PARENT(i)] ≤ A[i]。
2. bitwise operation
(1)shift(移位)
On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left by one bit position. Similarly, the RIGHT procedure can quickly compute 2i + 1 by shifting the binary representation of i left by one bit position and then adding 1. The PARENT procedure can compute ?i/2? by shifting i right one bit position.
看到這一段的時候突然懵了,不是說索引運算嗎?怎么突然就扯到位移了(bit)?原來乘以 2 等于該數(shù)的二進制表示左移一位,除以 2 等于右移一位(注:這里的移位是邏輯移位)。看來以前學的很多東西因為長期不運用都忘了。
二、英語總結(生詞:1)
1. point
(1)up to a point
idom. to a limited degree, to some extent(到一定程度,一定程度上)
示例:The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point(《算法導論(第4版)》第 161 頁)。
上面這句話的意思是:這個樹除了最底層可能不是完全填滿的,其它層都是完全填滿的,最底層從左到右依次填充至某個點。
“up to a point”在這里想表達“最底層的結點從左到右填充到一定程度”。
關于英語的注解同步更新匯總到 https://github.com/codists/English-In-CS-Books 倉庫。
三、其它
今天沒有什么想說的。
四、參考資料
1. 編程
(1) Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein,https://book.douban.com/subject/35591269/
2. 英語
(1) Etymology Dictionary:https://www.etymonline.com
(2) Cambridge Dictionary:https://dictionary.cambridge.org

歡迎搜索及關注:編程人(a_codists)
浙公網(wǎng)安備 33010602011771號