1

ヒープソートコードは次のように記述します。

興味深いのは

self.first, self.last = self.last, self.first

リストの先頭と末尾の 2 つの値を交換していませんself.list。

なんで？

#heapsort
import pdb
class heap(object):
    def __init__(self, list):
        super(heap, self).__init__()
        self.list = list
        self.heapify()
        if self.list:
            self.first = self.list[0]
            self.last = self.list[len(self.list)-1]
    def length(self):
        return len(self.list)
    def heap_node(self,i):
        large_i = i
        if 2*i+1<self.length() and self.list[2*i+1]>self.list[i]:
            large_i = 2*i+1
        if 2*i+2<self.length() and self.list[2*i+2]>self.list[large_i]:
            large_i = 2*i+2
        if large_i!=i:
            self.list[large_i], self.list[i] = self.list[i], self.list[large_i]
            self.heap_node(large_i)
    def heapify(self):
            for i in range(self.length()/2,0,-1):
                j=i-1
                self.heap_node(j)
    def sort(self):
        # pdb.set_trace()
        if not self.list:
            return []
        else:
            # self.list[0], self.list[len(self.list)-1] = self.list[len(self.list)-1], self.list[0]
            self.first, self.last = self.last, self.first 
            return heap(self.list[0:(self.length()-1)]).sort() + [self.list[len(self.list)-1]]

h=heap([1,3,2,5,4])
print h.list
print h.sort()
4

2 に答える 2

3

self.firstとは、とself.lastに含まれるデータの単なるコピーです。これらの値に直接割り当てる必要があります。self.list[0]self.list[-1]

self.data[0], self.data[-1] = self.data[-1], self.data[0]

負の配列インデックスを使用すると、Python はリストを最後から見ていきます。また、組み込みの name をシャドウイングする可能性を減らすために、 のdata代わりになどの名前を使用することをお勧めします。listlist

于 2012-06-30T19:07:03.067 に答える
2

そのはず self.list[0], self.list[-1] = self.list[-1], self.list[0]

self.firstとself.lastは からの最初と最後の値を含む単なる変数でありself.list、それらを変更しても変更されませんself.list

于 2012-06-30T19:06:02.073 に答える