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 Comparable>
  31. void buildHeap(Comparable arr[], int n, int d) {
  32.     // 1. The first index that might have children is n/d, not (n/d) - 1 !
  33.     //    Be careful of how integer division works ...
  34.     for (int i = (n/d); i>=0; --i){
  35.         sink(arr, i, n, d);
  36.     }
  37. }
  38.  
  39. template <typename Comparable>
  40. Comparable removeFromHeap(Comparable heap[], int n, int d) {
  41.     Comparable root = heap[0];
  42.     heap[0] = heap[n-1];
  43.     sink(heap, 0, n-1, d);
  44.     return root;
  45. }
  46.  
  47. template <typename T>
  48. void dheapsort(T arr[], int N, int d) {
  49.     buildHeap(arr, N, d);
  50.     while (N > 1) {
  51.         T tmp = removeFromHeap(arr, N, d);
  52.         arr[--N] = tmp;
  53.     }
  54. }
  55.  
  56. int main() {
  57.     int test[10] = {1, 3, 2, 5, 6, 8, 2, 8, 10, 11};
  58.     dheapsort(test, 10, 3);
  59.     for (int i = 0; i < 10; i++)
  60.         cout << "test[" << i << "] : " << test[i] << endl;
  61.     return 0;
  62. }
Success #stdin #stdout 0s 3296KB
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/jVS15I
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!