如何使用heapify将一个堆分成两个子堆进行heapsort？

Question

我正在尝试使用一些辅助函数在 python 中创建一个 HeapSort 函数。

我正在尝试按照我的书上的说明进行操作，并使用 fixHeap 等函数来恢复堆中节点不遵循规则的正确顺序：

def getMaxKnot(i,j,A):
    k = max(A[i],A[j])
    if k==A[i]:
        return i
    if k==A[j]:
        return j


def fixheap(v,H): #basically restore an heap with a node not following heap rules
    if (2*v+1)>len(H)-1:
        return H
    else:
        u=getMaxKnot(2*v+1,2*v+2,H)
        if H[u]>H[v]:
            listoperations.swap(u,v,H) #swap item in position u and v
        return fixheap(u,H)

现在，我基本上想创建一个 heapify 函数，它在左树和右树上递归工作，使用我的函数 fixheap 来恢复正确的顺序。

我的想法如下：

def heapify(A):
        if A==[]:
            return A
        else:
            heapify(LEFT TREE)
            heapify(RIGHT TREE)
            fixheap(0,A)

关于如何将数组 A 分成左树和右树有什么想法吗？

Answer 1

首先，fixheap 中缺少一些东西。假设节点 v 只有一个（左）子节点，那么 getMaxKnot 将触发无效索引错误，因为 j 会指向 A数组。

我个人认为 getMaxKnot 不值得作为一个单独的功能。我还将 fixheap 的参数按相反的顺序放置，这样第二个参数就可以很容易地省略并赋予默认值（当它是根元素时）。同样交换两个值实际上是一行：

def fixheap(H, v = 0): # put arguments in this order
    u = 2*v + 1
    if u >= len(H):
        return H
    if u+1 < len(H) and H[u+1] > H[u]: # Only compare when there are two child nodes
        u += 1
    if H[u] > H[v]:
        [H[u], H[v]] = [H[v], H[u]] # Swapping is easy
        return fixheap(H, u)

然后是你的主要问题：你的 heapify 也应该得到一个节点作为参数，这将是你想要堆化的子树的根。原理其实和fixheap函数的用法没有太大区别：

def heapify(H, v = 0):
    u = 2*v + 1
    if u >= len(H):
        return H
    heapify(H, u)
    if u + 1 < len(H): # make sure there is a right child
        heapify(H, u+1)
    fixheap(H, v)

如何使用heapify将一个堆分成两个子堆进行heapsort？

How to divide an heap into two sub-heap with heapify for heapsort?

python

recursion

heapsort

divide