fork(3) 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 = 19;
  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.     	int s = min_child(a, i, n);
  65.     	std::cout << "min_child called" << std::endl;
  66.     	while((s != 0) && (a[i] > a[s])){
  67.     		std::cout << "while loop" << std::endl;
  68.     		std::swap(a[i], a[s]);
  69.     		i = s;
  70.     		s = min_child(a, s, n);
  71.     	}
  72.     }
  73.  
  74.     //Преобразование массива в кучу
  75.     void build_dheap(int *a, int n){
  76.     	for(int i = (n - 1)/*/d*/; i >= 0; i--)
  77.     		siftdown(a, i, n);
  78.     	std::cout << "after siftdown" << std::endl;
  79.     }
  80.  
  81.     int main() {
  82.     	int a[SIZE];
  83.  
  84.     	for(int i = 0; i < SIZE; i++){
  85.     		a[i] = i % 10;
  86.     		std::cout << a[i] << " ";
  87.     	}
  88.     	std::cout << std::endl;
  89.  
  90.     	build_dheap(a, SIZE);
  91.  
  92.     	std::cout << std::endl;
  93.     	for(int i = 0; i < SIZE; i++)
  94.     		std::cout << a[i] << " ";
  95.  
  96.     	return 0;
  97.     }
Success #stdin #stdout 0s 3460KB
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 
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
min_child called
after siftdown

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