Skip to main content
 首页 » 编程设计

python之Python中堆数据结构如何实现max heapify

2024年12月31日18softidea

下面是堆类。我正在尝试对堆进行排序,但我的 max_heapify 函数有问题。我插入了值 [10, 9, 7, 6, 5, 4, 3] 并且我的堆排序打印给定的输出。给定的输出和期望的输出在类下面给出

堆的类别

class Heap(object): 
    def __init__(self): 
        self.A = [] 
 
    def insert(self, x): 
        self.A.append(x) 
 
    def Max(self): 
        """ 
        returns the largest value in an array 
        """ 
        return max(self.A) 
 
    def extractMax(self): 
        """ 
        returns and remove the largest value from an array 
        """ 
        x = max(self.A) 
        self.A.remove(x) 
        self.max_heapify(0) 
        return x; 
 
    def parent(self, i): 
        """ 
        returns the parent index 
        """ 
        i+=1 
        i = int(i/2) 
        return i 
 
    def left(self, i): 
        """ 
        returns the index of left child 
        """ 
        i = i+1 
        i = 2*i 
        return i 
 
    def right(self, i): 
        """ 
         returns the index of right child 
        """ 
        i+=1; 
        i = 2*i + 1 
        return i 
 
    def heap_size(self): 
        """ 
         returns the size of heap 
        """ 
 
        return len(self.A) 
 
    def max_heapify(self, i): 
        """ 
        heapify the array  
        """ 
        l = self.left(i) 
        r = self.right(i) 
 
        if(l < self.heap_size() and self.A[l] > self.A[i]): 
            largest = l 
        else: 
            largest = i 
 
        if(r < self.heap_size() and self.A[r] > self.A[largest]): 
            largest = r 
 
 
        if largest != i: 
 
            temp = self.A[i] 
            self.A[i] = self.A[largest] 
            self.A[largest] = temp 
 
            self.max_heapify(largest) 
 
 
    def build_max_heap(self): 
 
           n = len(self.A) 
           n = int(n/2) 
           for i in range(n, -1, -1): 
               self.max_heapify(i) 
 
 
    def heap_sort(self): 
        """ 
         sorts the heap 
        """ 
 
        while self.heap_size() > 0: 
 
                self.build_max_heap() 
                temp = self.A[0] 
                n = len(self.A) - 1 
                self.A[0] = self.A[n] 
                self.A[n] = temp 
                x = self.A.pop() 
                print(x) 
                self.max_heapify(0) 
 
 
 
 
h = Heap() 
h.insert(10) 
h.insert(9) 
h.insert(7) 
h.insert(6) 
h.insert(5) 
h.insert(4) 
h.insert(3) 
h.heap_sort()     

给定输出

10 
7 
6 
5 
4 
3 
9 

预期输出

10 
9 
7 
6 
5 
4 
3 

请您参考如下方法:

看起来您正在尝试构建一个根位于 A[0] 的最大堆。如果那是正确的,那么您的 left、right 和 parent 索引计算不正确。你有:

def parent(self, i): 
    """ 
    returns the parent index 
    """ 
    i+=1 
    i = int(i/2) 
    return i 
 
def left(self, i): 
    """ 
    returns the index of left child 
    """ 
    i = i+1 
    i = 2*i 
    return i 
 
def right(self, i): 
    """ 
     returns the index of right child 
    """ 
    i+=1; 
    i = 2*i + 1 
    return i 

因此,如果 i=0,则左 child 为 2,右 child 为 3。更糟糕的是,给定 i=3,parent 将返回 2。所以你遇到了 parent(right(i)) != i 的情况。这永远行不通。

正确的计算是:

left = (2*i)+1 
right = (2*i)+2 
parent = (i-1)/2 

我不知道为什么你的 extractMax 调用 max(self.A)。您已经知道最大元素位于 A[0]。要提取最大项,您需要做的就是:

returnValue = save value at self.A[0] 
take last item in the array and place at self.A[0] 
decrease length of array 
maxHeapify(0) 

我使用伪代码是因为我对 Python 不是特别满意。

heapSort 方法中的循环严重不理想。您在每次迭代时调用 self.build_max_heap。你不需要那样做。如果 extractMax 工作正常,您只需:

while self.heap_size() > 0: 
    temp = self.extractMax() 
    print temp 

现在,如果您想就地对数组进行排序,以便对 self.A 本身进行排序,那就有点棘手了。但看起来这并不是您想要做的。