1

この Heap-Sort のアルゴリズムに問題があります

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)
4

2 に答える 2

1

インプレースソートを行う場合...

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].

基本的にあなたのアルゴリズム。ただし、その場で並べ替えを行っていない場合は、単純に最小ヒープを使用して、すべての値を新しい配列にポップすることができます。

于 2010-07-14T15:47:18.797 に答える
0

最大要素をヒープ配列の後ろに移動してから削除すると、完了時に配列に何も残されません。したがって、最大値を削除するアルゴリズムは、元の要素の並べ替えられた配列にはなりません。

OP編集に基づく更新：

そのようにすることができます。ただし、最初の方法では、その場で並べ替えることができます。メソッドには、O(N) 個の追加ストレージが必要です。

別の編集：

最初のアルゴリズムでどのような仮定を行っているかを正確に把握することは困難ですが、以下で行ったコメントについて考えると、MaxHeapify(A,1)おそらくMaxHeapify(A, n). 通常、配列とそのサイズ、またはこの場合はヒープとして配置する要素の数を渡します。n がグローバル変数であると想定している場合、これは意味がないかもしれません。

于 2010-07-14T15:35:33.863 に答える