fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template <typename T>
  5. void sink(T arr[], int pos, int N, int d) {
  6.     int start(pos*d + 1), max_index(start);
  7.     while(start < N) {
  8.         // Find the max amongst direct "children" of position `pos`
  9.         for(int i = start + 1; (i < start + d) && (i < N); i++) {
  10.             if (arr[i] > arr[max_index]) {
  11.                 max_index = i;
  12.             }
  13.         }
  14.         // If arr[pos] is less than the max we found, switch them and proceed
  15.         if (arr[pos] < arr[max_index]) {
  16.             // Switch arr[pos] and arr[max_index] to enforce heap condition
  17.             T tmp = arr[pos];
  18.             arr[pos] = arr[max_index];
  19.             arr[max_index] = tmp;
  20.             // Update pos and start to sink "recursively"
  21.             pos = max_index;
  22.             start = pos*d + 1;
  23.             max_index = start;
  24.         } else { // Else, there is nothing to worry about further ...
  25.             break;
  26.         }
  27.     }
  28. }
  29.  
  30. template <typename T>
  31. void dheapsort(T arr[], int N, int d) {
  32.     // The for loop "heapify" the array.
  33.     for (int k = N/d; k >= 0; k--) {
  34.         sink<T>(arr, k, N, d);
  35.     }
  36.     // We exchange the max (located at arr[0] since the array became a heap)
  37.     // with the last element.
  38.     // Then we enforce the heap condition on the N-1 remaining elements.
  39.     // N is then decreased
  40.     // (...) so on.
  41.     while (N > 1) {
  42.         T tmp = arr[N-1];
  43.         arr[N-1] = arr[0];
  44.         arr[0] = tmp;
  45.         sink<T>(arr, 0, --N, d);
  46.     }
  47. }
  48.  
  49. // Then you just have to use it with the parameters you want ...
  50. // An example :
  51.  
  52. int main() {
  53.     int test[10] = {1, 3, 2, 5, 6, 8, 2, 8, 10, 11};
  54.     dheapsort(test, 10, 3);
  55.     for (int i = 0; i < 10; i++)
  56.         cout << "test[" << i << "] : " << test[i] << endl;
  57.     return 0;
  58. }
Success #stdin #stdout 0s 3340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test[0] : 1
test[1] : 2
test[2] : 2
test[3] : 3
test[4] : 5
test[5] : 6
test[6] : 8
test[7] : 8
test[8] : 10
test[9] : 11
https://ideone.com/ItEWFG
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!