这个算法有什么问题吗？

我有这个算法按堆排序这个算法有什么问题吗？

Heap_Sort(A) 
    Build_Heap(A) 
    for i<--n down to 2 
    swap (A[1],A[n]) 
    n<--n-1 
    MaxHeapify(A,1)

我觉得不是这个算法有问题，我们应该写：

Heap_Sort(A) 
    Build_Heap(A) 
    for i<-- n down to 1 
    Delete_Max(A)

来源

2010-07-14 user355002

与heapsort有关的问题的确切性质是什么？你为什么认为你应该删除最大值？ – mcandre 2010-07-14 15:31:53

我将所有这些删除的元素存储在一个数组中，将被排序 – user355002 2010-07-14 15:37:52

如果将最大元素添加到堆组的背面然后将其删除，完成后不会在数组中留下任何内容。因此，删除最大值的算法不会产生原始元素的排序数组。

更新基于OP编辑：

你可以做到这样。第一种方法，但是，可以让你排序。您的方法需要O（N）额外的存储空间。

另一个编辑：

这是很难看到你正在做的第一算法到底是什么假设，但我想我下面提出的意见，这很可能是MaxHeapify(A,1)也许应该MaxHeapify(A, n)。您通常会传递一个数组和它的大小，或者在这种情况下，您要将其排列为堆的元素的数量。如果你假定n是一个全局变量，这可能是没有意义的。

来源

2010-07-14 15:35:33 andand

对不起，我编辑了我的文章！我有一个错误 – user355002 2010-07-14 15:37:02

如果我交换[1]和[n]所以最大值会发生什么？ – user355002 2010-07-14 15:39:50

@ martin1234：交换允许算法排序。 n <-n-1只是说堆的大小已经减小，所以你找到的最大元素不会被重新插入到堆中（即它减小堆的大小）。 – andand 2010-07-14 15:53:59

如果你正在做一个就地排序...

Heap_Sort(A) 
    B = Build_Heap(A) # Assuming maxheap 

    for i -> A.length to 0: 
     Remove top value from B (which is basically just A, but treated differently), 
     assuming the heap is modified to maintain partial ordering during this part 
     (as well as decreasing the noted size of the heap by 1) and add the removed 
     value to position A[i].

基本上你的算法。但是，如果你没有进行排序，你可以简单地使用minheap，并将所有值弹出一个新的数组。

来源

2010-07-14 15:47:18 JAB

你的版本我有你的版本的问题，我认为有问题 – user355002 2010-07-14 15:56:26

@matin：是的，我redid算法。不过，我对这个堆本身应该如何工作做了一些假设。 – JAB 2010-07-14 15:58:22

这个算法有什么问题吗？

回答

相关问题