2

the python code is: 

def max_heapify(i, arr, n):
    l = 2*i
    r = 2*i+1
    largest = i
    if (2*i <= n-1 and arr[l] > arr[i]):
        largest = l

    if (2*i+1 <= n-1 and arr[r] > arr[largest]):
        largest = r
    if largest != i:
        temp = arr[largest]
        arr[largest] = arr[i]
        arr[i] = temp

        max_heapify(largest, arr, n)
    return arr

arr=[16,4,10,14,7,9,3,2,8,1]
n=len(arr)

#max_heapify(i,arr,n)
for i in range(n//2):
    max_heapify(n//2-1-i,arr,n)
4

1 回答 1

0

尝试这个

堆排序的 Python 程序

堆排序是一种基于二叉堆数据结构的比较排序技术。它类似于选择排序，我们首先找到最大元素并将最大元素放在最后。我们对剩余的元素重复相同的过程。

用于实现堆排序的Python程序

堆化以索引 i 为根的子树。

n 是堆的大小

def heapify(arr, n, i):

largest = i  # Initialize largest as root 

l = 2 * i + 1     # left = 2*i + 1 

r = 2 * i + 2     # right = 2*i + 2 



# See if left child of root exists and is 

# greater than root 

if l < n and arr[i] < arr[l]: 

    largest = l 



# See if right child of root exists and is 

# greater than root 

if r < n and arr[largest] < arr[r]: 

    largest = r 



# Change root, if needed 

if largest != i: 

    arr[i],arr[largest] = arr[largest],arr[i]  # swap 



    # Heapify the root. 

    heapify(arr, n, largest)

对给定大小的数组进行排序的主要功能

def heapSort(arr):

n = len(arr) 



# Build a maxheap. 

for i in range(n, -1, -1): 

    heapify(arr, n, i) 



# One by one extract elements 

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

    arr[i], arr[0] = arr[0], arr[i]   # swap 

    heapify(arr, i, 0)

上面测试的驱动代码

arr = [ 12, 11, 13, 5, 6, 7] 堆排序（arr）

n = len(arr)

print ("排序后的数组是")

对于范围内的 i (n)：

print ("%d" %arr[i]),

此代码由 Mohit Kumra 提供

输出：

排序后的数组是 5 6 7 11 12 13

于 2019-07-01T11:00:42.420 回答