なぜヒープソートの空間の複雑さはO（1）ですか？

Question

ヒープソートの空間の複雑さがどのようにO（1）であるのか分かりませんか？クイックソートでは余分な配列（すなわち、インプレース）は使用されませんが、最悪の場合はO（n）、再帰呼び出しの場合はバックエンドでスタックが使用されるため、O（lg n）が最適です。私は正しい？

同じことがヒープソートになります。しかし、それはインプレースですが、Build-Heap関数はMax-Heapify関数を呼び出しているので、空間複雑度はMax-Heapifyと等しくなければなりません。つまりO（lg n）です。ではない？また、後でMax-Heapify関数はルートノードでn回呼び出され、Max-Heapify（）空間の複雑さはO（lg n）となります。

したがって、ヒープソートの全体的な空間の複雑さは、O（lg n）でなければなりません。しかし、私はwikipediaでO（1）を見つけました。それを理解するのを助けてください。

Answer 1

Heapsortは、ソートされる配列のサイズ、配列自体のスペース、およびいくつかの変数に依存するスペースをとらない。明らかにO（1）。

クイックソートは、ソートが必要なサブアレイのスタックを追跡します。あなたが巧みで、2つのサブアレイのうち大きい方をスタックに置き、すぐに小さいものをソートすると、O（log n）がかかります。

実際には違いはありません。

Answer 2

スペース複雑さは、アルゴリズムで使用される余分なスペースを指します。ヒープソートは、ソートする配列以外の余分なスペース（O（n）内）を使用しません。それゆえ、O（1）

Answer 3

heapifyの再帰的バージョンはありません（下記の例を参照）。クイックソートの場合、再帰が小さいパーティションでのみ使用されている場合は、ループして大きなパーティションを2に分割し（2つのパーティションの小さい方のパーティションでも再帰を使用）、最大スタック領域はO（log n））、最悪の時間はまだO（n^2）です。非再帰heapify有する非再帰ヒープソートの

C++例：実装は愚かでない限り

typedef unsigned int uint32_t; 

void HeapSort(uint32_t *, size_t); 
void Heapify(uint32_t *, size_t); 
void SiftDown(uint32_t *, size_t, size_t); 

void HeapSort(uint32_t * a, size_t count) 
{ 
size_t end; 
    Heapify(a, count);  // create initial heap 
    end = count-1; 
    while(end > 0){ 
     // swap root (largest value) with end 
     std::swap(a[0], a[end]); 
     // reduce size of heap and 
     // increase size of sorted array 
     end--; 
     // repair the reduced heap 
     SiftDown(a, 0, end); 
    } 
} 

// create initial heap: for root = (count-2)/2 -> 0 
// parent = root, children = root*2+1, root*2+2 
// swap so that all a[parent] > a[child] 
void Heapify(uint32_t * a, size_t count) 
{ 
size_t root; 
    if(count < 2) 
     return; 
    // create sub-heaps of increasing size, 
    // with root going from (count-2)/2 to 0 
    root = (count - 2)/2; 
    while(1){ 
     SiftDown(a, root, count-1); 
     if(root == 0) 
      break; 
     root--; 
    } 
} 

// scan from root to end, swapping as needed to repair or create heap 
void SiftDown(uint32_t * a, size_t root, size_t end){ 
size_t parent; 
size_t child; 
    // while at least two children 
    for(parent = root; (child = parent * 2 + 2) <= end;){ 
     // choose the larger child 
     if(a[child-1] > a[child]) 
      child = child-1; 
     // if child > parent then swap, parent = child 
     if(a[child] > a[parent]){ 
      std::swap(a[child], a[parent]); 
      parent = child; 
     // else done with search for swaps 
     } else { 
      break; 
     } 
    } 
    // check for final only child 
    if((child = parent * 2 + 1) <= end) 
     if(a[child] > a[parent]) 
      std::swap(a[child], a[parent]); 
}