fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4.  
  5. int max_heapify(std::vector<int>& v, int i){
  6.  
  7. 	int l = 2*i;
  8. 	int r = 2*i + 1;
  9. 	int largest = 0;
  10.  
  11. 	if( (l < v.size()) && (v[l] > v[i]) ){
  12.  
  13. 		largest = l;
  14. 	}
  15. 	else{
  16. 		largest = i;
  17. 	}
  18.  
  19. 	if ( (r<v.size()) && (v[r] > v[largest]) ){
  20. 		largest = r;
  21. 	}
  22. 	if ( largest != i){
  23.  
  24. 		std::swap(v[i], v[largest]);
  25. 		max_heapify(v, largest);
  26. 	}
  27.  
  28. 	return 0;
  29. }
  30.  
  31.  
  32. int build_max_heap(std::vector<int> &v){
  33.  
  34. 	for( int i = v.size()/2; i >= 0; i--){
  35. 		max_heapify(v, i);
  36.  
  37. 	}
  38. 	return 0;
  39.  
  40. }
  41.  
  42. int heap_sort(std::vector<int>& v){
  43. 	build_max_heap(v);
  44. 	int length = v.size();
  45. 	for( int i = length-1 ; i>=1; i--)
  46. 	std::swap(v[0], v[i]);
  47. 	length--;
  48. 	max_heapify(v, v[length]);
  49.  
  50. }
  51.  
  52. int main(){
  53. std::vector<int> v = { 1, 2, 9, 8, 3, 4, 7, 6, 5};
  54. heap_sort(v);
  55.  
  56. for(auto& e : v) std::cout<<e<<" ";
  57.  
  58. return 0;	
  59. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8 5 7 3 4 1 6 2 9
https://ideone.com/4eD289
language:
C++14 (gcc 8.3)
created:
7 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!