7.1 heap -13
heap 是complete binary tree
子節(jié)點的數(shù)值不能大于它的父節(jié)點保證heap的根節(jié)點是最大的元素谆构，稱為max-heap
priority queues is a set (or pool) of elements
用array來存儲heap時
- H[1]是最大的數(shù)莱睁，eject的時間復(fù)雜度是O(1)+重新存儲heap的時間
- heap的高是log2(n)的向下取整锅睛，樹的高是log2(n)的向下取整忽舟，空樹高為-1.
- heap的parents節(jié)點為1 到n/2向下取整
7.1.1Injecting a New Item
1.Place the new item at the end; 將要加的節(jié)點添入末尾
2.let it “climb up”, repeatedly swapping with parents that are smaller讓其與較小的父節(jié)點對換使其攀升
3.This process has Ο(log n) complexity
7.1.2Building a Heap Bottom-Up
若此方法在已經(jīng)構(gòu)造好的heap上使用，不是新構(gòu)造heap日川，時間復(fù)雜度為O(n)
1.從最后一個父節(jié)點開始往前移
2.先找出最大的子節(jié)點
3.再將父節(jié)點與子節(jié)點比較蔓腐，若小于則將子節(jié)點的值換到父節(jié)點的位置上，但父節(jié)點的值先不變龄句，只有引用在變
4.直至父節(jié)點移動到正確的位置回论，在將父節(jié)點的值賦予引用的位置
full tree：number of nodes n=2^(h+1)-1
number of nodes at level i: 2^(h-i)
i為從下往上數(shù)的層數(shù)，leaves是level0分歇，root是level h
若此方法用于構(gòu)造一個新的heap
- use the inject operation repeatedly. 用inject n-1次
- the construction cost will be Ο(nlog n)
7.1.3 Ejecting a Maximal Element from a Heap
1.調(diào)換root節(jié)點和最后一個節(jié)點
2.對最后一個節(jié)點sift-down到正確的位置
3.被調(diào)換到最后的root節(jié)點不在是heap的一部分傀蓉，n遞減
時間復(fù)雜度為Ο(logn)
7.2 Heapsort（Build and Then Deplete a Heap）
1.將array變?yōu)镠eap
2.應(yīng)用eject n-1次
總結(jié)
1.heapsort時間復(fù)雜度為 Θ(n log n)
2.heapsort不stable，是in-place的
3.平均時間復(fù)雜度比quicksort慢卿樱，但性能更有保證
4.單個節(jié)點的增加與刪除復(fù)雜度都是Ο(logn)
5.在已有heap中排序復(fù)雜度是Ο(n)僚害，新建一個heap的復(fù)雜度是Ο(nlogn)
6.heapsort是先將數(shù)組的數(shù)字導(dǎo)入后再排序，不是直接建立一個heap
7.3Transform and Conquer-14
轉(zhuǎn)換:將問題修改為更易于處理的形式繁调，然后
征服:解決它使用已知的有效算法。
- 主要變量：
Instance simplification簡化實例
Representational change表征變化
Problem reduction 問題減少
7.3.1 Instance Simplification
一般原則:試著通過一些預(yù)處理靶草，特別是排序蹄胰，來簡化問題。
一下問題可以預(yù)先對輸入進行排序來加快速度奕翔，例如:
- Finding the median找到中位數(shù)
- Uniqueness checking唯一性檢查
- Finding the mode找到眾數(shù)
14-7 各算法對比
問題1：Uniqueness Checking
判斷array的數(shù)是否唯一
如果使用brute-force時間復(fù)雜度為Ο(n^2)裕寨，提前排序時間復(fù)雜度為Ο(nlogn)
14-8，未排序
14-23派继，提前排序 sort復(fù)雜度為Ο(nlogn)+尋找同樣的數(shù)Ο(n)
問題2：Finding the mode
找到眾數(shù)
提前排序時間復(fù)雜度為Ο(nlogn)
14-39宾袜，提前排序
問題3：在1024個數(shù)中找32個數(shù)
14-46
問題4： Finding Anagrams
anagram：用同樣的字母但排序不同。例 ate/tea/eat
14-48
7.4 Binary Search Tree
A binary search tree驾窟，BST庆猫，左子數(shù)皆小于根節(jié)點，右子樹皆大于根節(jié)點
If a BST with n elements is “reasonably” balanced, search involves in the worst case, Θ(log n) comparisons.
對BST執(zhí)行Inorder遍歷將生成其已排序的元素秩序绅络。
