شكراً على المشاركة بالحل، لم أفكر بإستعمال min heap، نسيت أغلب Data structures.

insort تقوم بعمل binary search، المشكل انني أقوم بعمل pop(0) (كمبليكستي او(N)) إذاً صحيح كما قلت أنت O(N^2 log N) أحسنت، ولكن يمكن أن تكون O(N log N) إذا تم إستعمال stack و- binary search، شكراً مرة أخرى على مشاركة الحل.

لا أعرف لماذا لكن حلك الذي يعمل بال-min heap أسرع من BS + stack

def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

def k(f):
    s = 0
    while len(f) != 1:
        p = f.pop() * f.pop()
        s += p
        reverse_insort(f, p)
    print(s)

a = range(1, 10 ** 5)
a.sort(reverse=True)
k(a)

$ /usr/bin/time -v python /home/mo/a.py > /dev/null
Command being timed: "python /home/mo/a.py"
User time (seconds): 5.83
System time (seconds): 0.14
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.99
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10576
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2612
Voluntary context switches: 1
Involuntary context switches: 96
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

-

$ cat b.py
from heapq import heappush, heappop

heap = []
for i in xrange(1, 10 ** 5):
    heappush(heap, i)

energy = 0
while len(heap) > 1:
    mul = heappop(heap) * heappop(heap)
    energy += mul
    heappush(heap, mul)

print(energy)

$ /usr/bin/time -v python /home/mo/b.py > /dev/null
Command being timed: "python /home/mo/b.py"
User time (seconds): 4.10
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:04.11
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10688
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2589
Voluntary context switches: 1
Involuntary context switches: 67
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

ملاحظة bisect ليس فيه reverse