how to convert binary heap sort to d_ary heap sort?

Question

Hi I have an algorithm that uses binary tree to heapify and then sort the list i need to convert this sort algorithm to change into d-heap or d-ary heap or k-ary heap my code is here

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)

please help

Answer 1

Add the d parameter to all your functions, and generalise. The formula for where to start the heapify function is (num + 1) // d - 1. Where you have left and right indices and choose the one that has the greatest value, instead iterate the children in a for loop to find the child with the greatest value.

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)