移動minheap.top到maxheap.top其中maxheap.top <= minheap.top

我有一個maxheap和minheap其中maxheap的最大元素小於或等於所述minheap的最小元素。移動minheap.top到maxheap.top其中maxheap.top <= minheap.top

我現在想移動minheap的最小元素成爲maxheap的最大元素。要做到這一點

的一種方法是，以彈出minheap的頂部元素，並把它壓入maxheap。

有沒有更有效的方法來做到這一點？

以下是我最後做：

其實我有插入一個元素minheap然後執行上述操作，我做了以下內容：

// place value to insert at end of minheap 
mintoph[mintoph_size] = R; 

// use std::pop_heap, minimum element now at end 
pop_heap(mintoph.begin(), mintoph.begin() + mintoph_size + 1, greater<int>()); 

// (*) make room in maxheap at top 
for (int pos = maxboth_size++; pos > 0;) 
{ 
    int parent = (pos - 1)/2; 
    maxboth[pos] = maxboth[parent]; 
    pos = parent; 
} 

// move element from back of minheap to maxheap head 
maxboth[0] = mintoph[mintoph_size];

有一個在上面的步驟(*)處浪費已付費的比較，因爲父母被降級爲子女，但我認爲這是不可避免的。

來源

2012-07-06 Andrew Tomazos

我不認爲有「交叉優化」的基礎上的事實，你有兩個數據結構的任何方式;畢竟，他們都必須獨立地維護它們的不變量（當然，除非您準備轉向不同的數據結構）。我認爲唯一可以幫助你的事情就是你要插入的物品保證是最大的。 – 2012-07-06 19:25:35

順便提一下，您的問題標題（「maxheap.top to minheap.top」）與您的問題主體不符（「移動minheap的最小元素...」）。 – 2012-07-06 19:30:11

實際上我想去兩個方向，但它是一個鏡像，所以一種方式將提供另一種方式。 – 2012-07-06 19:32:37

你真正需要的是插入到優先級隊列的有效方式，當你知道要插入的元素比最小值/最大值小/大，這取決於是否該是最小堆還是最大堆。對於傳統的「堆」數據結構，這需要O（log n）時間。

但是，如果你願意用不同的表現比傳統的「堆」的數據結構中的優先級隊列，則可以平凡作出這樣的插入到爲O（1）運行時間。許多不同類型的優先級隊列都可以做到這一點，例如左堆，傾斜堆或配對堆。

編輯：當然，您仍然需要支付從原始優先級隊列中移除的費用，無論如何這可能是O（log n），儘管也有一些方法可以幫助解決這個問題，例如「懶惰刪除」。

來源

2012-07-07 22:09:13

具體而言，要將已知最小的元素插入實現爲左堆的最小堆中，請創建一個包含插入元素的新根節點，將舊根作爲其左側子元素，並將其右側子元素留空。 – dfeuer 2012-07-14 04:52:46

-1

使用最小 - 最大堆，這是一個雙端優先隊列，你可以做這件事情在O（LGN），你不能這樣做，在不到O（LGN）

但你可以用攤餘算法他們做O（1）像斐波那契堆插入，

來源

2012-07-06 19:25:24 Pooya

你明白'maxheap.top <= minheap.top'而不是'minheap.top <= maxheap.top'吧？ – 2012-07-06 19:28:50

是的，我可以，但是你不能在低於lgn的情況下做到這一點 – Pooya 2012-07-06 19:38:35

你可以在最大堆中插入你的節點作爲葉，然後調用你的heapify函數 – Pooya 2012-07-06 19:43:52

你會可能是最好用最小 - 最大堆或樹堆服務。 min-max-heap似乎是爲你正在做的事情量身定製的，但是trevers是如此全面，以至於它們也可能運行得很好 - 尤其是如果你需要的不僅僅是查找最小值和最大值以及增加值時。

http://en.wikipedia.org/wiki/Min-max_heap

http://en.wikipedia.org/wiki/Treap

來源

2012-07-06 23:05:48 user1277476

這是不正確的，如果我需要最小值和最大值相同的一組數值比minmax堆適當。問題是關於兩個分開的集合，其中最小的一個是> =另一個的最大值。 – 2012-07-07 01:11:22

移動minheap.top到maxheap.top其中maxheap.top <= minheap.top

回答

相關問題