!=
@apu629phy
Tue, Sep 7, 2021 10:03 AM
Tue, Sep 7, 2021 10:06 AM
[資結廢]
這應該是設計用來合併多個單向佇列的資料結構...吧?
binomial heap:
先從binomial tree開始介紹，反正這棵樹的性質全身都是二項式定理有關的，最後才去定義binomial heap是一個binomial tree的集合(Forest)，且為min-tree
其中merge的基本運算尤為重要，但是不同的課本有不同的操作，分勤奮的和懶惰的合併(?，刪最小和插入都是基於這個合併運算來完成的，各版本的差異就差在何時在哪個基本運算執行勤奮的合併(?
Horowitz是說當一個伺服器突然關閉時，另一個伺服器可以接收並合併它的event queue，不過我好奇的是這個實作是要由programmer還是OS會自動處理
掰噗~
@baipu
說
Tue, Sep 7, 2021 10:03 AM
這個問題問得很好, 我們請樓下來回答
!=
@apu629phy
Tue, Sep 7, 2021 10:09 AM
Fibnacci heap:
在binomial heap的基礎上增加2個運算: Delete x、Decrease-key of x
!=
@apu629phy
Tue, Sep 7, 2021 10:10 AM
Decrease-key of x上又說對於圖演算法有著關鍵的加速作用?
載入新的回覆
這應該是設計用來合併多個單向佇列的資料結構...吧?
binomial heap:
先從binomial tree開始介紹，反正這棵樹的性質全身都是二項式定理有關的，最後才去定義binomial heap是一個binomial tree的集合(Forest)，且為min-tree
其中merge的基本運算尤為重要，但是不同的課本有不同的操作，分勤奮的和懶惰的合併(?，刪最小和插入都是基於這個合併運算來完成的，各版本的差異就差在何時在哪個基本運算執行勤奮的合併(?
Horowitz是說當一個伺服器突然關閉時，另一個伺服器可以接收並合併它的event queue，不過我好奇的是這個實作是要由programmer還是OS會自動處理
在binomial heap的基礎上增加2個運算: Delete x、Decrease-key of x