Heap operation
Heap 是一種電腦程序演算的資料結構。有其適用的場合所以筆者花了不少時間試寫了兩支小程式。其實學生時就有寫過，程式碼若有找到再補 PO 上來。現在又重寫了一次，並詳加說明以免日後又忘了。。。
像這種基礎必要的東西例如資料結構都必須要留存可以複用的。當然可以使用 C++ template lib 或 C 函式庫才是正解。
Heap 簡介
- Heap tree 的簡稱，典型的是完整二元樹（complete binary tree）。基於此，特色是可排序，且可“就地排序”（in-place sort），即，在一線性陣列上不需額外的儲存空間即可於其上排序。“完整”是指樹的建構方式是由上而下由左而右。既然是樹為何上述扯到一維陣列？因，如此“完整”的建構方式，使得可一對一對應到一維陣列上面。細節請谷歌。
- 結構：在 binary heap tree 上，任何一個節點都必大於等於其鄰（下）接的子節點，稱為 max-heap tree，或都必小於等於其鄰（下）接的子節點，稱為 min-heap tree。
- 因此，必然，根節點（root）必是所有節點當中的極值（最大值或最小值）
- 而我們所關注的，也就只有根節點這顆，不管樹有上千萬顆節點，真的只有根節點這顆。
- 因此，關於 heap，關於資料結構的操作，就是在此樹中增加資料（增加一顆節點）以及刪除資料（刪除一顆節點）；然而此操作必破壞此樹的結構，故有重整樹的程序使得維持 heap 結構。刪除想當然爾就是刪根節點，因是我們唯一關注的。增加就是按規則加於樹的第一個葉節點（一維陣列由左至右首先遇到的第一個空位置。此空位後面不可能還存在資料）。之後再重整樹。
- 增加一顆節點，只需花費 log n 的時間，時間花在重整樹，就能把樹整理好。
- 同理刪除一顆節點也是 log n。
- 而利用它來排序，是當今已知最好的演算法之一。時間複雜度 n log n。
- （另外還有一個排序的性質就是同 key，heap 是否可維持其先後的關係，筆者就未查證了，判斷是的）。
- 排序就很直觀了：每次刪除一顆節點將其排下來，直到樹刪光，所排下來者就是有序列了。
min-heap insertion
void min_heap_insertion(unsigned key, unsigned *t){ // t[0] must be the current size
unsigned i=++t[0], j=(i>>1);
for (; j && t[j]>key; t[i]=t[j], i=j, j>>=1);
t[i]=key;
}
// 插入，只有唯一的位置就是樹的第一個葉節點，或說，若樹的節點由上而下由左而右依次編流水號，
// 那麼該位置就是最大號節點的下一個位置，空位，對應到陣列，必然是陣列中當前元素數目的大小 t[0]+1，的位置 t[ t[0]+1 ]，
// 因為筆者將 t[0] 佔用以為當前元素數目故須加一表示第一個沒有元素的空位。來存放即將加入的元素。
// 接著重整：若此新加入者，new_node，它的父節點比它還要小，則，收工，因為如此既有符合 heap 定義。
// 萬一沒有，則將 new_node 與父節點交換（其實是父節點下移），則交換後，以 new_node 為根的子樹必符合 heap 定義，因為，
// 原父節點既已滿足 heap，且父是該子樹中的極值，故它下移同樣保有 heap property。
// 然而，此時 new_node 所在的新的位置，可能已破壞 new_node 回溯回去的樹的 heap property，（一顆老鼠屎），
// 或說，此時的 heap 視同從 new_node 所在新的位置置換成了（加入了）這顆 new_node，當然，如此程序便形成迴圈，
// 簡單講，我們用個想像，若 new_node 是所有節點當中最小值，是不是將須一路循著父節點檢查或置換回到根節點，屆時，
// new_node 就是放在根節點。min-heap removal
unsigned min_heap_removal(unsigned *t){ // t[0] must be the current size
///if (!t[0]) return -1;
unsigned key=t[1];
unsigned i=2, j=1, k=t[0];
for (; i<k; j=i, i<<=1){
if (t[i]>t[i+1]) ++i;
t[j]=t[i];
}
t[j]=t[k]; /// 這行，於是可以被註解掉，因為下三行已 cover 了這一行了。
/// 假設沒有下面這個問題，則此行就可以 cover 所有狀況含邊際條件。
/// 故請全盤以本行思考整個程式，再來想下面三行所應對的問題。
/// 或者也可以留本行，並註解掉下三行，看程式結果會發生什麼狀況。
// 而這三行，就是為了處理當空出來的位置是任一葉節點時，等同插入重整樹。
t[0]=j-1;
min_heap_insertion(t[k], t);
t[0]=k-1;
return key;
}
// 根節點當然就是須移除者，且空出位置來。
// 唯有 i<k，才能比對某節點的兩個子節點，其中，若較小者則上移，
// 則下一次迴圈進來時所看 j 者就是上一次上移所空出來的，如此程式形成第一個迴圈。其結束時，j 位置仍是空位待填。
// 故最後 j 必然是葉節點（i>k），或只有一個左子節點（i==k）其意謂著是最後一個元素。然而，若是葉節點將可能是任何一個葉節點。
// (請試想像著一個百萬顆節點成一個等腰三角形樹，再加掛了三顆進去。此時 j 是所有葉節點中的一個，任何一個都有可能)
// 若是左子節點，則也是終節點，則直接填入空位不會破壞 heap。
// 若是任何葉節點，則將終節點填入那個葉節點空位，是的，可能會破壞 heap，
// 因 heap 只有一個那個性質。此葉節點跟終節點可能距離十萬八千里遠對吧。
// 最後來看程式本身的邊際條件，檢視 size==0，1，2 都成立。
//
// 將其展開如下：
/*
unsigned min_heap_removal(unsigned *t){ // t[0] must be the current size
///if (!t[0]) return -1;
unsigned key=t[1];
unsigned j=2, i=1, k=t[0]--;
for (; j<k; i=j, j<<=1){
if (t[j]>t[j+1]) ++j;
t[i]=t[j];
}
for (j=(i>>1); j && t[j]>t[k]; t[i]=t[j], i=j, j>>=1);
t[i]=t[k];
return key;
}
*/範例測試
void min_heap_insertion(unsigned key, unsigned *t, unsigned t_dat_length){ // t[0] must be the current size
if (t[0]==t_dat_length) return;
unsigned i=++t[0], j=(i>>1);
for (; j && t[j]>key; t[i]=t[j], i=j, j>>=1);
t[i]=key;
}
unsigned min_heap_removal(unsigned *t){ // t[0] must be the current size
if (!t[0]) return -1;
unsigned key=t[1];
unsigned i=2, j=1, k=t[0];
for (; i<k; j=i, i<<=1){
if (t[i]>t[i+1]) ++i;
t[j]=t[i];
}
t[j]=t[k]; /// 這行，於是可以被註解掉，因為下三行已 cover 了這一行了。
/// 假設沒有下面這個問題，則此行就可以 cover 所有狀況含邊際條件。
/// 故請全盤以本行思考整個程式，再來想下面三行所應對的問題。
/// 或者也可以留本行，並註解掉下三行，看程式結果會發生什麼狀況。
// 而這三行，就是為了處理當空出來的位置是任一葉節點時，等同插入重整樹。
t[0]=j-1;
min_heap_insertion(t[k], t, j);
t[0]=k-1;
return key;
}
void setup() {
Serial.begin(115200);
}
void loop() {
unsigned a[36];
String v="";
a[0]=0;
// 可將其啟用，看結果，以思考 heap 的適用場合
#if 0
for (int i=0; i<10000; i++){
if (random(12)%3) min_heap_insertion(random(60), a, 35);
else min_heap_removal(a);
}
#endif
while (a[0]<35) min_heap_insertion(random(60), a, 35);
for (int j=1; j<36; j++){v+=a[j]; v+=" ";}
printf("\r\n\r\n%s\r\n", v.c_str());
v="";
while (a[0]){v+=min_heap_removal(a); v+=" ";}
printf("%s\r\n\r\n", v.c_str());
delay(3000);
}範例輸出
20201120 補充
讓我們再來看看一個有趣的問題。
之所以當初會有這篇 heap operation，就是為了要實作之後文章的關於 ESP8266 計時器共享問題。而現下，heap operation 確實完全幫助了筆者此實作 ESP8266 MultiTimers。
但，筆者的 MultiTimers 遇到 bug 了。在呼叫了 sync functions 之後，偶爾莫名數值會錯亂掉。經勘錯，發現問題確實出現在 sync functions；如下述便明。
binary heap tree，我們只有關注根節點／也只能關注之。但萬一，tree 中某節點數值改變了，勢必破壞了整顆樹的秩序。而這情況在實務上確實是有可能遇到的，就如本例 MultiTimers。故，我們不得不加入思考這第四個問題：heap-sort，heap-insertion，heap-removal，及 heap-deterioration（筆者亂取的名稱，因為學校沒有教）。
min-heap deterioration
- 思考：
- 筆者現在才想了起來，重整樹 heapify 有兩種舉措，bottom-up heapify and top-down heapify。
- removal 時根節點空了，接著再從根為父節點的兩顆子節點當中，選出最小者當成父節點，而從子轉變成父的，的此子節點，便成為新的子樹的根節點，如此即成迴圈。此即稱為 top-down heapify of removal。此 removal 在 top-down 完成後，尚需一步從最後一顆葉節點拿來填補空缺並再重整樹一次，bottom-up heapify of removal。如此才完成整個 removal，故，removal，需 top-down，bottom-up 各做一次。
- 而 insertion，就簡單了，只要 bottom-up 整一次即成。
- 但 deterioration 呢？若能由 removal and insertion 兩種行為組合而成則再美好不過了。
- 該目標節點，筆者簡稱為 detor，又分為三種情況，若比原來小，若比原來大（MultiTimers），不知比原先大或小，思考的邏輯便不一樣，知大小或許可以簡化邏輯路徑但用途狹限。因此採通用就是不管大小。
- 須注意，在 heap insertion/removal 兩支程式（簡稱 impI，impR）中全程都是使用 index 定位，是絕對的概念。故，拿它們倆處理任何子樹，可能就不是同一回事了；因為一維陣列 index 與樹的節點編號 noden 是一對一絕對對應的。但子樹的 index & noden 顯然是對不上了，可說，index 跑掉了，原應 (idx0, n1), (idx1, n2), (idx2, n3), (idx3, n4)，子樹中，(idxi, n1), (idx2i, n2), (idx2i+1, n3), (idx4i, n4)。而實際上，呵～可說有跑掉也並沒有跑掉。簡曰，若把 0 這個絕對關係從程式中移除／若有的話，那麼，就沒有跑掉，程式直接延用。故，呵～筆者當前這兩支程式是須要修改的，必須改掉 0 點的絕對關係。
- min-heap deterioration：
- 步驟A，detor 子樹中，先視為 deter 被移除，先放到一邊，接著在 top-down 階段，如果補拿真正的（全樹的）最後一顆葉節點，筆者簡稱 la-leaf，將破壞的是 impR 邏輯，因 la-leaf 可能不會在此子樹中（但若在此子樹中則必是最後一顆葉節點沒錯）。故，將 impR 完全套用在子樹上則沒有問題，於 top-down 階段結尾，將是産生該子樹所屬的最後一顆葉節點（簡稱 vla-leaf）是個空缺，因 vla-leaf 拿去補 top-down 空缺了。接著第二階段 bottom-up。待結束，則已做了一整套 removal 程序並留了個空缺，是子樹的最後一個葉點 vla-leaf。對了忘了，還有提取出來的 detor。
- 步驟B，拿 detor 補 vla-leaf，則等同又要做一次 removal 的 buttom-up 程序，或說做一次 insertion 程序，並完成之。
- 是故，好像全完成了。
- 因此簡單講，deterioration 便是由一個 removal 及一個 insertion 就可完成之。
- 但發現到了嗎？我們似乎忽略了，當初根本不需以 vla-leaf 來補空缺，而是 detor 就可勝任。
- 因此，
- 步驟一：移除 detor 子樹的根 detor
- 步驟二：removal 的 top-down 程序，留了個空缺
- 步驟三：detor 取代 vla-leaf，補上了這個空缺
- 步驟四：removal 的 bottom-up 程序
- 結果筆者發現，寧可採取此四步驟也不願只做那兩步驟有點違反世間常理XD
程式考量
- 筆者當然想延用原程式，不過，從絕對改為相對，interface，即函式介面勢必要改掉，即，會與原函式不同。
- 子樹的 vla-leaf 與主樹的 la-leaf 不見得相同，主樹的，在函式介面外便可見／已知。而子樹的資訊該從何而來？我們不得不搜尋之。
- 做 deterioration 節點並沒有增加或減少，這是對我們最好的消息。只要按步就班做好一步（等同一整套 removal）即成並不怕樹被破壞。再者，子樹的 vla-leaf 要不是 la-leaf，要不就是子樹將是一顆完全樹（full binary tree，即，一棵正等腰三角形，不缺任何節點，即，底邊最右側節點一定存在，且就是 vla-leaf），這將是提供給我們搜尋的唯一資訊，但，別忘了我們並不需要它，而是需要知道它是子樹最後一顆節點（終止條件）。但此處再讓我們反回來想，終止條件就是 <= la-leaf 或 <= vla-leaf，再下次一迴圈（乘 2）皆必大於二者，且皆必大於全樹最終節點，換言之，搜尋此舉全然不必要，只要拿樹的 size 來比即可。
- 因此，整個程式將拿 removal 程式來改，且程序一模一樣，只差一些中繼條件及邊際條件及相對性。
void min_heap_deterioration(unsigned new_key, unsigned idx_target, unsigned *t){ // t[0] must be the current size
// t is the whole tree, the min-root is t[1]. t[0] is used for as the tree size.
// the idx_target ranges from 1 to t[0].
// new_key will replace in the t[idx_target], and then this tree will be rearranged well.
unsigned j=(idx_target<<1), i=idx_target, k=t[0];
for (; j<k; i=j, j<<=1){
if (t[j]>t[j+1]) ++j;
t[i]=t[j];
}
// at this point, divided into 2 conds., the empty slot is either the last-leaf's parent or some leaf without child.
// we can treat separated or unify in one. so the latter is choosed; or say, it covered both.
if (t[k]<new_key){ // so swap
t[i]=t[k];
t[k]=new_key;
new_key=t[i];
}
for (j=(i>>1); (j>=idx_target) && t[j]>new_key; t[i]=t[j], i=j, j>>=1);
t[i]=new_key;
}20230125 補充
最近在整理資料從 cd 備份片搬家到 usb-disk。真的以前蒐集的東西太多了。。。可能要十輩子才看得完XXD。。。
翻出以前寫的 heap sort，並也有 qsort。附於下。
quick sort worst case n^2，所以筆者偏好 heap sort 複雜度始終為 nlog(n) 且 stable sort。對了，當思考看看 stable quick sort 及它的 non-recursive 版本兩個問題（遺憾的是。。。下輩子了XXD）。
而某教本 quick sort 也有寫錯，犯了眾人所構病的 c array 越邊界問題。自己寫的因有發現而有留意排除此問題。當說，規範沒有問題，問題在於人／態度。重點是，努力是一時的（腦袋才不會生鏽），成果卻是持續永遠的；即，個人頗不認同加料去避險，即便只一滴滴，犧牲卻是龐大的／永遠的；簡單講，簡單就是美，計結聖經內有提到。。。。