title: Heap Sort Space Complexity
body: <p>I was just reading through Skiena's Algorithm Design Manual book, in particular the section on Heap Sort. He states that </p>
  
  <blockquote>
    <p>It is an in-place sort, meaning it uses no extra memory over the array containing the elements to be sorted</p>
  </blockquote>
  
  <p>the algorithm in the book looks like this:</p>
  
  <pre><code>heapsort(item_type s[], int n) 
  {
    int i;
    priority_queue q;
  
    make_heap(&amp;q, s, n);
  
    for (i=0; i&lt;n; i++) 
      s[i] = extract_min(&amp;q);
  }
  </code></pre>
  
  <p>To me, it looks like in addition to the input array <code>s</code> of items, we're creating a heap data structure in the <code>priority_queue</code> variable. Doesn't this mean that the required space complexity is O(n) and requires approximately double the memory, not "no extra memory"?</p>