[問題] heapsort

[mqazz1 (無法顯示)]

Let A be an array of n arbitrary and distinct numbers

A has the following property: If we imagine B as being sorted version of A,
then any element that is at position i in array A would, in B,
be at a position j such that |i–j| <= k

In other words, each element in A is not farther than k positions away from
where it belongs in the sorted version of A

Suppose you are given such an array A, and you are told that A has this
property for a particular value k (that value of k is also given to you)

Design an O(n lg k) time algorithm for sorting A.


網路上的解法是這樣: http://algnotes.wordpress.com/2010/06/08/150/

可是我看不太懂這樣跟2k有甚麼關係@@

請問有人可以舉簡單的例子來說明網路的解法嗎?

還是有更好的方法呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.166.118.32
推 springman:那個答案是對的。只是我總覺得應該建 k+1 個元素的
→ springman:minimum heap 就可以，為什麼需要 2k 個元素呢？
→ springman:將最小的 k+1 個元素建成一個 minimum heap
→ springman:輸出最小值、並再加下一個元素進來
→ springman:重複一直做應該就可從小輸出到大才對
→ springman:從中間做起才需要用到 2k 個元素