迭代子列表堆排序python实现 [英] Iterative in place sub-list Heap Sort python implementation

问题描述

我为python找到了不同版本的堆排序，但似乎找不到符合我需要的版本.

I've found different versions of heap sort for python, but I can't seem to find the one that matches my needs.

迭代堆排序是我找到的最接近的， 但我不太清楚如何更改它以使用子列表 (索引起点，索引终点)并保持不变.

Iterative Heap Sort is the closest I found, but I can't quite figure out how to change it to work with a sub-list (index start, index end) and remain in place.

如果我做对了，那么我将在这里发布答案.

If I get it right then I'll post my answer here.

如果有人甚至可以用C或Java来实现，那都很棒.

If anyone has an implementation in even C or Java that will be great.

推荐答案

我设法做自己想做的事情. 该代码适用于对象，并按特定属性进行排序.

I managed to do what I want. This code works on objects and sorts by a specific attribute.

def buildMaxHeap(arr, arrayLength, indexStart, attr):
    for i in range(arrayLength):

        # if child is bigger than parent
        if getattr(arr[indexStart + i], attr) > getattr(arr[indexStart + int((i - 1) / 2)], attr):
            j = i

            # swap child and parent until
            # parent is smaller
            while getattr(arr[indexStart + j], attr) > getattr(arr[indexStart + int((j - 1) / 2)], attr):
                (arr[indexStart + j],
                 arr[indexStart + int((j - 1) / 2)]) = (arr[indexStart + int((j - 1) / 2)], arr[indexStart + j])
                j = int((j - 1) / 2)


def heapSort(arr, arrayLength, indexStart, attr):
    buildMaxHeap(arr, arrayLength, indexStart, attr)

    for i in range(arrayLength - 1, 0, -1):

        # swap value of first indexed
        # with last indexed
        arr[indexStart + 0], arr[indexStart + i] = arr[indexStart + i], arr[indexStart + 0]

        # maintaining heap property
        # after each swapping
        j, index = 0, 0

        while True:
            index = 2 * j + 1

            # if left child is smaller than
            # right child point index variable
            # to right child
            if (index < (i - 1) and getattr(arr[indexStart + index], attr) < getattr(arr[indexStart + index + 1], attr)):
                index += 1

            # if parent is smaller than child
            # then swapping parent with child
            # having higher value
            if index < i and getattr(arr[indexStart + j], attr) < getattr(arr[indexStart + index], attr):
                arr[indexStart + j], arr[indexStart + index] = arr[indexStart + index], arr[indexStart + j]

            j = index
            if index >= i:
                break

这篇关于迭代子列表堆排序python实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！