我想知道是否有人可以幫我解決這個問題。我正在使用C/C++編程，我需要執行以下操作：插入和刪除陣列中的元素，同時保持要排序的陣列
我給出了一個包含浮點數的排序數組P（最大的第一個）。它通常有一個非常大的尺寸..有時候會保存來自1000萬像素圖像的相關值。我需要迭代數組，直到它爲空。在循環內還有額外的處理。
問題的關鍵是，在循環的開始，我需要從數組中刪除具有最大值的元素，檢查某些條件，如果它們持有，那麼我需要重新插入元素到數組中但在降低其價值之後。但是，我想要在重新插入後對數組進行高效排序。
有人可以指出我這樣做嗎？我嘗試過每次插入時重新排序的幼稚方法，但這看起來非常浪費。
更改數據結構。重複訪問最大元素，然後快速插入新值，以便仍可以高效地重複訪問最大元素，這是heap的一項工作，可能是fairly easily created from your array in C++。
順便說一句，請不要談論「C/C++」。沒有這樣的語言。你反而會對你寫作的風格產生模糊的含義，其中大部分會對有經驗的程序員造成不良影響。
您可以使用二進制搜索來確定從數組中刪除更改後的值的位置。請注意，在前面或中間的某處插入或移除效率不高，因爲它需要分別向上或向下移動索引較高的所有項目。
ISTM，你應該把你的改變的項目放到一個新的數組中，並且在完成對原始數組的迭代之後排序一次。如果記憶是一個問題，並且您確實需要做某些事情，請更改這些值並只進行一次排序。
我想不出一個更好的方法來做到這一點。保持數組一直排序似乎效率很低。
也許使用另一個臨時陣列可能會有所幫助。
這樣，您可以先單獨對「已更改」元素進行排序。
之後，只需將兩個子數組的O（n）合併到temp數組中，然後將所有數據都複製回原始數組。
它必須每次合併，這比僅僅重新插入相同的數據要慢。 –
但據我所知，他需要從數組中刪除具有最大值的元素，然後在降低它們的值後將它們重新插入到數組中。因此，所有「更改」的值將立即被接收......這意味着只需要一次合併... –
是的，但合併不能到位，這意味着您必須觸摸3N數據。通過某種簡單的移位插入（如vector :: insert），可以觸及UP TO N。 –
我想看看http://www.cplusplus.com/reference/stl/priority_queue/，因爲它是爲了做到這一點而設計的。
由於數組已經排序，所以可以使用二進制搜索來查找插入更新值的位置。 C++爲此提供了std::lower_bound或std::upper_bound，C提供了bsearch。只需將所有現有值向上移動數組中的一個位置，並將新值存儲在新清除的點上。
我想，必須將所有元素全部移入插入，幾乎可以抵消將事物排序在第一位的好處。無論哪種方式，每次都是O（N），並且使用'std :: lower_bound'只是一個常數因素的改進。 –
@Karl，非常真實。 –
@Karl在最糟糕的情況下，它是O（N）。根據情況，這可能是一個可以接受的解決方案（它恰好是我想的完全一樣的東西！）如果數組包含的值如100 99 96 90 85 82 80 ...並且值正在減少，說10 - 這樣做並不是太糟糕。編輯：馬克的回答可能有點誤導，因爲它說你必須改變「所有現有的元素」。例如，在按降序排列的數組中，您只需移動大於調整值的元素，如我在答案中所述。 –
下面是一些僞代碼，可能體面的工作，如果你沒有減少被許多刪除值：
例如，假設您正在處理與數組中的最大值的元素，並說出陣列按降序排列（最大的第一個）。
刪除array[0]。
讓newVal = array[0] - adjustment，其中adjustment是你減少值的數量。
現在遍歷，僅調整需要的值：
僞代碼：
i = 0
while (newVal < array[i]) {
array[i] = array[i+1];
i++;
}
array[i] = newVal;
swap(array[i], array[i+1]);
同樣，如果你沒有大量減少去除值（相對到數組中的值），這可以非常有效地工作。
當然，通常更好的選擇是使用更合適的數據結構，如堆。
「通常更好的選擇是使用更合適的數據結構，比如堆。」似乎是重要的一部分。 –
horray for heaps！ –
術語'heap'在C和C++中有另一個更常見的含義，更徹底的描述或鏈接將會有所幫助。 –
@Mark True。修訂。 –