從wikipedia：優先級隊列O（n）的分類列表實現的插入時間複雜度是多少？
排序列表實現：就像在超市收銀臺 線，但 其中重要的人拿到 前不太重要的人「開刀」。 （爲O（n） 插入時間，O（1）獲得，接下來的時間， O（N *的log（n））建）
我認爲，如果搜索與二進制搜索算法插入位置，插入時間複雜度應該是O（log（n））。在這裏，我把工作到達順序作爲優先級的一個因素。
所以我錯了或維基百科不正確？
更新： 根據列表從TAOCP嚴格定義：
線性列表爲n> = 0 節點X 1的序列，X [2]，...，其中 必不可少的結構性質 只涉及 之間的相對位置，因爲它們出現在 行中。
我承擔列表維基百科是指不鏈表，它可能是陣列。
謝謝。
如果它的鏈接列表支持，你不能做二分法搜索; 找到插入點是O（n），實際插入的是O（1），因爲您只需更改相鄰節點，即 整體O（n）。
如果它的數組支持，你可以做二進制搜索， 找到插入點是O（的log（n））， 但在陣列中插入是O（n）作爲可能需要在陣列中的所有元素移位， 整體爲O（n）
這是爲什麼你實際上有樹/堆的支持，所以所有的操作都可以是O（log（n））
thanks.i沒有考慮到移動之前的節點:) – Jichao 2010-02-01 17:01:39
看來，在您的報價中，維基百科指的是一個由排序列表支持的優先級隊列，而不是堆。要插入一個項目到一個排序列表中需要O（n）個時間（假設我們正在維護它的排序）。
我不這麼認爲。列表應該在插入之前排序。這就是爲什麼構建的時間複雜度爲O（n * log（n）），這是通用排序算法的時間複雜度。 – Jichao 2010-02-01 16:22:35
@jcyang考慮列表'1 - > 2 - > 3 - > 4'並嘗試手動插入元素'5'。請注意，您沒有隨機訪問權限（沒有'list [3]'，只有'list-> next'） – laura 2010-02-01 16:27:25
@laura：列表不是鏈接列表。它只是通常作爲鏈接列表（單獨或雙向鏈接）或數組。因此，如果我將prority樹實現爲數組，那麼我可以隨機訪問。 – Jichao 2010-02-01 16:35:07
排序列表中的最差情況插入時間爲O（n）。最糟糕的情況是將最高的項目插入列表中。爲此，您必須遍歷所有元素，然後在最後插入。您無法進行二分搜索的原因是您只能在列表中訪問的元素是當前元素的後繼元素，即無法隨機訪問。
維基百科是對的。正如其他人在這裏已經說過的，列表不是隨機訪問的，因此您需要在訪問B之前訪問A和B之間的每個節點。這使得二進制搜索無用，因爲遍歷列表是O（n），所以最終做更多工作比如果你只是迭代列表一次。您可以將開始，中間和結束節點緩存到單獨的緩衝區中並首先檢查這些節點。但是，這與使用多個列表的效果相同。跳過列表數據結構將這一想法向前推進了一步。
因此，根據您的需要，使用隨機存取堆或跳過列表：http://en.wikipedia.org/wiki/Skip_list。
你能發佈鏈接到你引用的維基百科文章嗎？ – 2010-02-01 15:58:04
啊，我爲你做了這項工作。這是優先隊列文章：http://en.wikipedia.org/wiki/Priority_queue – 2010-02-01 15:59:51