Databases
StackOverflow2013
Postsdbo
POC++ heapsort confusion
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC++ heapsort confusion
    text
    copied!<p>This might be a weird question but I'm trying to figure out why the following code works.</p> <p>It seems as though this code should be used where the heap elements index starts at 1 but it's starting at 0 and the sort is completed correctly.</p> <p>I say that because the left child is calculated as (element*2) and the right child is (element*2 + 1). This would make the left child for the element with index 0 also have index 0.</p> <pre><code>#include &lt;iostream&gt; using namespace std; void siftDown(int numbers[], int root, int bottom) { int done, maxChild, temp; done = 0; while ((root*2 &lt;= bottom) &amp;&amp; (!done)) { if (root*2 == bottom) maxChild = root * 2; else if (numbers[root*2] &gt; numbers[root*2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (numbers[root] &lt; numbers[maxChild]) { temp = numbers[root]; numbers[root] = numbers[maxChild]; numbers[maxChild] = temp; root = maxChild; } else { done = 1; } } } void heapSort(int numbers[], int n) { int i, temp; for (i = n/2; i &gt;= 0; i--) { siftDown(numbers, i, n - 1); } for (i = n-1; i &gt;= 1; i--) { temp = numbers[0]; numbers[0] = numbers [i]; numbers [i] = temp; siftDown(numbers, 0, i-1); } } int main() { int cases; int n; int count; cin &gt;&gt; cases; for (int i=0; i &lt; cases; i++) { cin &gt;&gt; n; int array[n]; for (int j=0; j &lt; n; j++) { cin &gt;&gt; array[j]; } heapSort(array, n); for (int k=0; k &lt; n; k++) { cout &lt;&lt; array[k]; } cout &lt;&lt; endl; } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload