Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 366: / Line 366: @@
 <pre>
 -199 -52 2 3 33 56 99 100 177 200
+</pre>
+{{trans|CoffeeScript}}
+Uses C++11. Compile with
+  g++ -std=c++11
+<lang cpp>
+#include <iostream>
+#include <vector>
+using namespace std;
+void shift_down(vector<int>& heap,int i, int max) {
+    int i_big, c1, c2;
+    while(i < max) {
+        i_big = i;
+        c1 = (2*i) + 1;
+        c2 = c1 + 1;
+        if( c1<max && heap[c1]>heap[i_big] )
+            i_big = c1;
+        if( c2<max && heap[c2]>heap[i_big] )
+            i_big = c2;
+        if(i_big == i) return;
+        swap(heap[i],heap[i_big]);
+        i = i_big;
+    }
+}
+void to_heap(vector<int>& arr) {
+    int i = (arr.size()/2) - 1;
+    while(i >= 0) {
+        shift_down(arr, i, arr.size());
+        --i;
+    }
+}
+void heap_sort(vector<int>& arr) {
+    to_heap(arr);
+    int end = arr.size() - 1;
+    while (end > 0) {
+        swap(arr[0], arr[end]);
+        shift_down(arr, 0, end);
+        --end;
+    }
+}
+int main() {
+    vector<int> data = {
+, 11, 15, 10, 9, 1, 2,
+, 13, 14, 4, 5, 6, 7, 8
+    };
+    heap_sort(data);
+    for(int i : data) cout << i << " ";
+}</lang>
+{{out}}
+<pre>
+2 3 4 5 6 7 8 9 10 11 12 13 14 15
 </pre>