fork download
copy 
  1.     #include <iostream>
  2.     using namespace std;
  3.  
  4.     #include <algorithm>
  5.     #include <iostream>
  6.  
  7.     #define SIZE 20
  8.  
  9.     const int d = 3;
  10.  
  11.     //Всплытие
  12.     void siftup(int *a, int i){
  13.     	int p = (i - 1) / d;
  14.     	while((i != 0) && (a[p] > a[i])){
  15.     		std::swap(a[i], a[p]);
  16.     		i = p;
  17.     		p = (i - 1) / d;
  18.     	}
  19.     }
  20.  
  21.     //n - длина массива
  22.     int min_child(int *a, int i, int n){
  23.     	if(i*d + 1 >= n) return 0;
  24.     	else{
  25.     		int s = i*d + 1;
  26.     		int min_key = a[s];
  27.     		int last = (i + 1)*d;
  28.     		if(last >= n) last = n - 1;
  29.     		for(int j = s+1; j <= last; j++){
  30.     			if(min_key > a[j]){
  31.     				min_key = a[j];
  32.     				s = j;
  33.     			}
  34.     		}
  35.     		return s;
  36.     	}
  37.     }
  38.  
  39.     int min_child2(int *a, int i, int n){
  40.     	int minchild = 0;
  41.  
  42.     	std::cout << "start minchild2" << std::endl;
  43.  
  44.     	if(i*d + 1 > n) return 0;
  45.     	else{
  46.     		int first_child = i*d + 1;
  47.     		int last_child = std::min((1 + i)*d - 1, n);
  48.     		int min_key = a[first_child];
  49.  
  50.     		std::cout << "else minchild2" << std::endl;
  51.     		for(int i = first_child; i <= last_child; i++)
  52.     			if(a[i] > min_key){
  53.     				min_key = a[i];
  54.     				minchild = i;
  55.     				std::cout << "for loop minchild2" << std::endl;
  56.     			}
  57.     		std::cout << "return minchild2" << std::endl;
  58.     		return minchild;
  59.     	}
  60.     }
  61.  
  62.     //Погружение
  63.     void siftdown(int *a, int i, int n){
  64.     	std::cout << "siftdown called: i=" << i << std::endl;
  65.     	int s = min_child(a, i, n);
  66.     	std::cout << "min_child called: a[" << i << "]=" << a[i] << " result=" << s << std::endl;
  67.     	while((s != 0) && (a[i] > a[s])){
  68.     		std::cout << "swap i=" << i << " s=" << s << std::endl;
  69.     		std::swap(a[i], a[s]);
  70.     		i = s;
  71.     		s = min_child(a, i, n);
  72.       	    std::cout << "min_child called: a[" << i << "]=" << a[i] << " result=" << s << std::endl;
  73.     	}
  74.     }
  75.  
  76.     //Преобразование массива в кучу
  77.     void build_dheap(int *a, int n){
  78.     	for(int i = (n - 1)/*/d*/; i >= 0; i--)
  79.     		siftdown(a, i, n);
  80.     	std::cout << "after siftdown" << std::endl;
  81.     }
  82.  
  83.     int main() {
  84.     	int a[SIZE];
  85.  
  86.     	for(int i = 0; i < SIZE; i++){
  87.     		a[i] = i % 10;
  88.     		std::cout << a[i] << " ";
  89.     	}
  90.     	std::cout << std::endl;
  91.  
  92.     	build_dheap(a, SIZE);
  93.  
  94.     	std::cout << std::endl;
  95.     	for(int i = 0; i < SIZE; i++)
  96.     		std::cout << a[i] << " ";
  97.  
  98.     	return 0;
  99.     }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 
siftdown called: i=19
min_child called: a[19]=9 result=0
siftdown called: i=18
min_child called: a[18]=8 result=0
siftdown called: i=17
min_child called: a[17]=7 result=0
siftdown called: i=16
min_child called: a[16]=6 result=0
siftdown called: i=15
min_child called: a[15]=5 result=0
siftdown called: i=14
min_child called: a[14]=4 result=0
siftdown called: i=13
min_child called: a[13]=3 result=0
siftdown called: i=12
min_child called: a[12]=2 result=0
siftdown called: i=11
min_child called: a[11]=1 result=0
siftdown called: i=10
min_child called: a[10]=0 result=0
siftdown called: i=9
min_child called: a[9]=9 result=0
siftdown called: i=8
min_child called: a[8]=8 result=0
siftdown called: i=7
min_child called: a[7]=7 result=0
siftdown called: i=6
min_child called: a[6]=6 result=19
siftdown called: i=5
min_child called: a[5]=5 result=16
siftdown called: i=4
min_child called: a[4]=4 result=13
swap i=4 s=13
min_child called: a[13]=4 result=0
siftdown called: i=3
min_child called: a[3]=3 result=10
swap i=3 s=10
min_child called: a[10]=3 result=0
siftdown called: i=2
min_child called: a[2]=2 result=7
siftdown called: i=1
min_child called: a[1]=1 result=4
siftdown called: i=0
min_child called: a[0]=0 result=3
after siftdown

0 1 2 0 3 5 6 7 8 9 3 1 2 4 4 5 6 7 8 9
https://ideone.com/DRblj9
language:
C++ (gcc 8.3)
created:
8 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!