3

従来のHeapsortアルゴリズムは、ヒープの最後の要素を現在のヒープのルートと毎回スワップしheapification、プロセスを再び続行します。しかし、私はそれが一種の不要であることに気付きました。

サブ配列の の後heapification、ノードに最大値が含まれている間 ( の場合max-heap)、配列内の次の 2 つの要素は、現在と同じ順序で、またはそれらを交換して、並べ替えられた配列のルートに従う必要があります。それらが逆にソートされている場合。したがって、ルートを最後の要素と交換するだけでなく、最初の 3 つの要素 (ノードを含み、必要に応じて 2 番目と 3 番目の要素を交換した後) を最後の 3 つの要素と交換する方がよいのではないでしょうか。後続のheapifications(2 番目と 3 番目の要素の) は省かれますか?

この方法に不利な点はありますか (必要に応じて 2 番目と 3 番目の要素を交換することは簡単です)。そうでない場合、それが実際に優れている場合、パフォーマンスはどの程度向上しますか? 疑似コードは次のとおりです。

function heapify(a,i) {
  #assumes node i has two nodes, both heaps. However node i itself might not be a heap, i.e one of its children may be greater than its value.
  #if so, find the greater of its two children, then swp the parent with that value.
  #this might render that child as no longer a heap, so recurse
 }

function create_heap(a) {
   #all elements following index |_n/2_| are leaf nodes, thus heapify() should be applied to all elements within index 1 to |_n/2_|
   }

function heapsort(a) {
  create_heap(a);  #a is now a max-heap
  #root of the heap, that is a[1] is the maximum, so swap it with a[n].
  #The root now contains an element smaller than its children, both of which are themselves heaps.
  #so apply heapify(a,1). Note: heap length is now n-1, as a[n] is the largest element already found
  #now again the array is a heap. The highest value is in a[1]. Swap it with a[n-1].
  #continue
  }

配列が であるとし[4,1,3,2,16,9,10,14,8,7]ます。を実行するheapifyと、 になり[16,14,10,8,7,9,3,2,4]ます。これで、heapsortの最初の繰り返しで 16 と 4 が入れ替わり、 になり[4,14,10,8,7,9,3,2,16]ます。これで新しいヒープのルートが[4,14,10,8,7,9,3,2]、うーん、ヒープされていない (14 と 10 はどちらも 4 より大きい) としてレンダリングされたので、別の実行を実行heapifyして を生成し[14,8,10,4,7,9,3,2]ます。これで 14 がルートになり、2 と交換して yield[2,8,10,4,7,9,3,14]になり、配列を currently にし[2,8,10,4,7,9,3,14,16]ます。ここでも 2 が非ヒープであることがわかります。そのため、再び a を実行するheapifyと、ヒープが になります[10,8,9,4,7,2,3]。次に、10 が 3 と交換され、配列が になり[3,8,9,4,7,2,3,10,14,16]ます。要点は、16 の前に 10 と 14 を格納するために 2 番目と 3 番目の s を実行する代わりにheapification、最初の s からわかるということです。heapification10 と 14 は 16 に続くため、2 番目と 3 番目に大きい要素です (またはその逆)。したがって、それらを比較した後 (既にソートされている場合は、14 が 10 より前になります)、そこにあるすべてを で交換し(16,14,10)、 (3,2,4)配列を作成し[3,2,4,8,7,9,16,14,10]ます。これにより、現在と比較して、さらに2つheapificationのsの後の状態と同様の状態になります。どちらもさらに が必要になりますが、2 番目の方法では、2 つの要素 (14 と 10) を比較するだけで、この時点に直接到達できます。[3,8,9,4,7,2,3,10,14,16][3,2,4,8,7,9,16,14,10]heapification

4

1 に答える 1

10

ヒープの 2 番目に大きい要素は 2 番目または 3 番目の位置に存在しますが、3 番目に大きい要素はさらに下の深さ 2 に存在する可能性があります。 ( http://en.wikipedia.org/wiki/Heap_(data_structureの図を参照) ) ) )。さらに、最初の 3 つの要素を最後の 3 つの要素と交換した後、heapify メソッドは、最初にルートの最初のサブツリーをヒープ化し、次にルートの 2 番目のサブツリーをヒープ化し、その後にツリー全体をヒープ化します。したがって、この操作の総コストは、最上位の要素を最後の要素と交換して heapify を呼び出すコストの 3 倍近くになります。したがって、これを行っても何も得られません。

于 2012-09-19T21:48:31.947 に答える