gpt4 book ai didi

algorithm - 我用于构建最小堆的 Heapsort 算法有什么问题?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:14:16 25 4
gpt4 key购买 nike

我正在为软件开发人员面试做准备,并且一直在研究算法问题。我的书展示了一种 Heapsort 算法,它可以按升序对无序数组进行排序。我正在尝试修改它,以便它可以使用最小堆进行排序。但是当我按照代码中的逻辑进行操作时,它并没有正确排序我的数组。我的代码(伪代码)有什么问题?

The array to be sorted: 16, 14, 10, 8, 7, 9, 3, 2, 4, 1

书中的 Heapsort 算法使用 max-heapify:

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length down to 2
swap A[1] with A[i]
A.heapsize = A.heapsize - 1
MAX-HEAPIFY(A, 1)

MAX-HEAPIFY(A)
l = Left(i)
r = Right(i)
if l <= A.heapsize and A[l] > A[i]
largest = l
else
largest = i
if r <= A.heapsize and A[r] > A[largest]
largest = r
if largest != i
swap A[i] with A[largest]
MAX-HEAPIFY(A, largest)

我使用 min-heapify 修改的代码:

HEAPSORT(A)             // where A is an array
BUILD-MIN-HEAP(A)
for i = A.length down to 2
swap A[1] with A[i]
A.heapsize = A.heapsize + 1
MIN-HEAPIFY(A, 1)

MIN-HEAPIFY(A, i)
l = Left(i)
r = Right(i)
if l <= heapsize.A and A[l] < A[i]
smallest = l
else
smallest = i
if r <= heapsize.A and A[r] < A[smallest]
smallest = r
if smallest != i
swap A[i] with A[smallest]
MIN-HEAPIFY(A, smallest)

最佳答案

堆排序分两个阶段运行:(1) 将未排序的数组转换为堆,(2) 将堆转换为已排序的数组。

为了构建堆,for 循环应该从 2 运行到 A.length; 并且堆大小应该变大,而不是变小。

BUILD-MAX-HEAP(A) 的代码片段似乎适用于第 2 阶段,用于从堆中构建排序数组。

阶段 1 将通过让新节点在堆中“冒泡”来在数组的开头构建堆。只要新节点比其父节点大(如果生成最小堆,则小于),就与其父节点交换它。

关于algorithm - 我用于构建最小堆的 Heapsort 算法有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24487726/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com