如何将二进制堆排序转换为d_ary堆排序？

Question

嗨，我有一种算法，该算法使用二进制树来堆积，然后对我需要转换此类算法的列表将其更改为D-Heap或d-ary heap或k-ary heap 我的代码在这里

def build_heap(lista, num):
    """Function to construct heap."""
    for i in range(num // 2 - 1, -1, -1):
        heapify(lista, num, i)


def heapify(lista, num, index):
    """Function to heapify list."""
    largest = index
    left = (2 * index) + 1
    right = (2 * index) + 2

    if left < num and lista[largest] < lista[left]:
        largest = left

    if right < num and lista[largest] < lista[right]:
        largest = right

    if largest != index:
        lista[index], lista[largest] = lista[largest], lista[index]
        heapify(lista, num, largest)


def heapsort(lista,d=2):
    """Function for final Heap sort."""
    length = len(lista)
    build_heap(lista, length)

    for i in range(length - 1, 0, -1):
        lista[i], lista[0] = lista[0], lista[i]
        heapify(lista, i, 0)

请帮忙

Answer 1

将d参数添加到您的所有功能中，并概括。在哪里开始堆功能的公式为（num + 1）// D -1。在哪里有左和右索引，然后选择具有最大价值的索引，而是在 loop中迭代儿童以找到孩子具有最大的价值。

def build_heap(lista, d, num):
    for i in range((num + 1) // d - 1, -1, -1):
        heapify(lista, d, num, i)


def heapify(lista, d, num, index):
    largest = index
    for child in range(d * index + 1, min(num, d * index + d + 1)):
        if lista[largest] < lista[child]:
            largest = child

    if largest != index:
        lista[index], lista[largest] = lista[largest], lista[index]
        heapify(lista, d, num, largest)


def heapsort(lista, d=2):
    length = len(lista)
    build_heap(lista, d, length)

    for i in range(length - 1, 0, -1):
        lista[i], lista[0] = lista[0], lista[i]
        heapify(lista, d, i, 0)