如何就地实现堆排序？

您可以采取以下步骤使其就位：

• 使堆可以只作用于给定列表的一部分，忽略不属于这部分的值。为此，引入一个size属性，该属性以与 相同的值开始len(contents)，但可以由堆的用户减少。这意味着您还需要：

  • 替换每次使用len(self), 或len(self._data)self.size
  • 将is_empty方法移动到子类中，这实际上完全不需要子类。

• 将创建堆的新实例的部分替换为：

  self.size -= 1
  self._downheap(0)
  

  • 因此，您不再需要构造函数中的以下部分：

    if isinstance(contents[0],self._Item):
        self._data = contents
        print("the slice passed in",self)
    

更新代码：

from queue import Empty

class HeapPriorityQueue():  # Subclassing removed
    class _Item():
        __slots__ = "_key","_value"
        def __init__(self, k,v):
            self._key = k
            self._value = v
        
        def __lt__(self,other):
            return self._key < other._key
        
        def __str__(self):
            return str(self._key) +" "+ str(self._value)
    
    def is_empty(self):
        return self.size == 0  # use self.size
        
    def _parent(self,j):
        return (j-1) // 2
        
    def _left(self,j):
        return 2*j+1
        
    def _right(self,j):
        return 2*j+2
        
    def _has_left(self,j):
        return self._left(j) < self.size  # use self.size
        
    def _has_right(self,j):
        return self._right(j) < self.size  # use self.size
        
    def _swap(self,i,j):
        self._data[i],self._data[j] = self._data[j],self._data[i]
        
    def _upheap(self,j):
        parent = self._parent(j)
        if j>0 and self._data[j] > self._data[parent]:
            self._swap(j,parent)
            self._upheap(parent)
            
    def _downheap(self,j):
        if self._has_left(j) and self._has_right(j):
            left = self._data[self._left(j)]
            right = self._data[self._right(j)]
            if left > right:
                if self._data[self._left(j)] > self._data[j]:
                    self._swap(j,self._left(j))
                    self._downheap(self._left(j))
            else:
                if self._data[self._right(j)] > self._data[j]:
                    self._swap(j,self._right(j))
                    self._downheap(self._right(j))
        elif self._has_left(j):
            if self._data[self._left(j)] > self._data[j]:
                self._swap(j,self._left(j))
                self._downheap(self._left(j))
        
    # ---------------------public methods----------------------
    def __init__(self,contents=[]):
        self.size = len(contents)
        # Removed support for _Item instances in contents
        self._data = [self._Item(k,v) for k,v in contents]
        if len(self._data) > 1:
            self._heapify()
            print("after heapifying the slice",self)
            
    def __len__(self):
        return len(self._data)
        
    def add(self,key,value):
        i = self._Item(key,value)
        self._data.append(i)
        self._upheap(self.size-1)   # use self.size
        
    def max(self):
        if self.is_empty():
            raise Empty("Priority queue is empty")
        item = self._data[0]
        return (item._key,item._value)
        
    def remove_max(self):
        if self.is_empty():
            raise Empty("Priority queue is empty")
        self._swap(0,self.size-1)  # use self.size
        item = self._data.pop()
        self._downheap(0)
        return (item._key,item._value)
        
    def _heapify(self):
        start = self._parent(self.size-1)  # use self.size
        for i in range(start,-1,-1):
            self._downheap(i)
            
    def __iter__(self):  # Warning: Does not take size into account
        for i in self._data:
            yield i
            
    def __str__(self):  # Warning: Does not take size into account
        l = [str(i) for i in self._data]
        return " ".join(l)

    def sort(self):
        l = len(self._data)
        for i in range(1,l):
            self._swap(0,l-i)
            print(self)
            # now it's in-place. 
            self.size -= 1
            self._downheap(0)
            print(self)
        return self._data


c = ((6,"Iris"), (3,"Helen"),(1,"Frank"),(4,"Joy"),(2,"Daniel"),(5,"Mark"))
h = HeapPriorityQueue(c)
s = h.sort()
for i in s:
    print(i)