Question

Randomly generates N distinct integers with N provided by the user, inserts all these elements into a priority queue, and outputs a list L consisting of all those N integers, determined in such a way that:

• inserting the members of L from those of smallest index to those of largest index results in the same priority queue;
• L is preferred in the sense that the last element inserted is as large as possible, and then the penultimate element inserted is as large as possible, etc.

Sample outputs

$ python3 qui z 1 0 . py
Enter 2 nonnegat ive i n t e g e r s , the second one no g r e a t e r than 100: 0 3
The heap that has been gene rat ed i s :
[None , 27 , 12 , 2 4 ]
The p r e f e r r e d o rde r ing o f data to g ene r at e t h i s heap by s u c c e s s s i v e i n s e r t i o n i s :
[ 1 2 , 24 , 2 7 ]
$ python3 qui z 1 0 . py
Enter 2 nonnegat ive i n t e g e r s , the second one no g r e a t e r than 100: 0 5
The heap that has been gene rat ed i s :
[None , 48 , 24 , 26 , 2 , 1 6 ]
The p r e f e r r e d o rde r ing o f data to g ene r at e t h i s heap by s u c c e s s s i v e i n s e r t i o n i s :
[ 2 , 26 , 48 , 16 , 2 4 ]
$ python3 qui z 1 0 . py
Enter 2 nonnegat ive i n t e g e r s , the second one no g r e a t e r than 100: 0 7
The heap that has been gene rat ed i s :
[None , 65 , 53 , 62 , 33 , 49 , 5 , 5 1 ]
The p r e f e r r e d o rde r ing o f data to g ene r at e t h i s heap by s u c c e s s s i v e i n s e r t i o n i s :
[ 3 3 , 49 , 5 , 53 , 62 , 51 , 6 5 ]
$ python3 qui z 1 0 . py
Enter 2 nonnegat ive i n t e g e r s , the second one no g r e a t e r than 100: 0 10
The heap that has been gene rat ed i s :
[None , 97 , 61 , 65 , 49 , 51 , 53 , 62 , 5 , 38 , 3 3 ]
The p r e f e r r e d o rde r ing o f data to g ene r at e t h i s heap by s u c c e s s s i v e i n s e r t i o n i s :
[ 5 , 53 , 62 , 33 , 38 , 65 , 97 , 49 , 51 , 6 1 ]
$ python3 qui z 1 0 . py
Enter 2 nonnegat ive i n t e g e r s , the second one no g r e a t e r than 100: 0 15
The heap that has been gene rat ed i s :
[None , 149 , 130 , 129 , 107 , 122 , 124 , 103 , 66 , 77 , 91 , 98 , 10 , 55 , 35 , 7 2 ]
The p r e f e r r e d o rde r ing o f data to g ene r at e t h i s heap by s u c c e s s s i v e i n s e r t i o n i s :
[ 6 6 , 91 , 10 , 107 , 122 , 35 , 55 , 77 , 130 , 98 , 149 , 124 , 129 , 72 , 103]

思路

因为要保证L里从后往前的数字是尽量最大的，因此可以从L的最后一个数字往前倒着做，最后reverse一下即可。因为L里的数字都是一个个往大根堆最后插，再上浮到相应的位置，造成的数据移动发生且只发生在“从插入位置上浮到它定下来的位置这条路“上。而我们又不知道它定在了哪，只知道堆的末尾在哪，我们可以逆推，看看堆的最后一个有没有可能是被移动过的，若它比兄弟小，不可能被移动，否则不满足堆的性质；若它不小于它的兄弟（或无兄弟），则可能被移动，而它的父节点一定比它大，要出现也是它的父节点出现在L中而不是它自己，因此它一定被移动。根据这个推理，我们就可以归纳出算法：从堆的最后一个节点开始往前回溯，可以上移（比兄弟大或兄弟不存在）就上移，不能上移的，被挤出来的那个数字就入L，然后堆就少了一个数字。往复做这件事，L的逆就算出来了。最后reverse一下，就是答案。

代码

仅供参考，请勿抄袭，防止查重。

def preferred_sequence():
    L=[]
    for i in range(len(pq),0,-1): # L从后往前遍历
        if i==1:L.append(pq._data[i]);
        else:
            p=i
            max_num=pq._data[i] # 记录目前待上移的数
            pq._data[i]=None # 堆的末节点置空
            while p>1:
                if p % 2 == 0 and pq._data[p + 1] is not None and pq._data[p + 1] > max_num: break # p是一个左子节点，若其右兄弟存在且比它大，则不能上移
                if p % 2 == 1 and pq._data[p - 1] > max_num: break # p是一个右子节点，若其左兄弟比它大，则不能上移
                # 上移并记录新数
                tmp = max_num
                max_num = pq._data[p // 2]
                pq._data[p // 2] = tmp
                p=p//2 # p找到父亲
            L.append(max_num)
    L.reverse()
    return L

时间复杂度

遍历堆复杂度O(n)，每个点回溯复杂度O(logn)，故总复杂度为O(n*logn)。