標籤: Data Structure

Heap operation

No Comments

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 越邊界問題。自己寫的因有發現而有留意排除此問題。當說,規範沒有問題,問題在於人/態度。重點是,努力是一時的(腦袋才不會生鏽),成果卻是持續永遠的;即,個人頗不認同加料去避險,即便只一滴滴,犧牲卻是龐大的/永遠的;簡單講,簡單就是美,計結聖經內有提到。。。。

PHP Code Snippets Powered By : XYZScripts.com