《算法導論(第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)