fork download
copy 
  1. #include<stdio.h>
  2. void heapify(int a[], int i);
  3. void build_heap(int a[]);
  4. void heapsort(int a[]);
  5. int left(int i);
  6. int right(int i);
  7. int a[1000001]; // increased size since given in problem t<=10^6
  8. int length;
  9. int main()
  10. {
  11.     int i;
  12. 	scanf("%d",&length);
  13. 	for(i=0;i<length;i++)
  14. 	{
  15. 		scanf("%d",&a[i]);
  16. 	}
  17. 	build_heap(a);
  18. 	heapsort(a);
  19. 	return 0;
  20. }
  21. void build_heap(int a[])
  22. {
  23.   int i;
  24. 	for(i=(length-1)/2;i>=0;i--)
  25.     heapify(a,i);
  26. }
  27.  
  28. int left(int i)
  29. {
  30. 	return 2*i+1;
  31. }
  32.  
  33. int right(int i)
  34. {
  35. 	return 2*i+2;
  36. }
  37.  
  38. void heapify(int a[], int i)
  39. {
  40. 	int l=left(i);
  41. 	int r=right(i);
  42. 	int largest, store;
  43. 	if (l<length && a[l]<a[i])
  44. 		largest=l;
  45. 	else
  46. 		largest=i;
  47.  
  48. 	if(r<length && a[r]<a[largest])
  49. 		largest=r;
  50. 	if (largest!=i)
  51. 	{
  52. 		store=a[largest];
  53. 		a[largest]=a[i];
  54. 		a[i]=store;
  55. 		heapify(a,largest);
  56.     }
  57. }
  58.  
  59. void heapsort(int a[])
  60. {
  61. 	build_heap(a);
  62. 	int i,store;
  63. 	for(i=(length-1);i>=0;i--)
  64. 	{
  65. 		store=a[0];
  66. 		a[0]=a[i];
  67. 		a[i]=store;
  68. 		printf("%d\n",a[i]);
  69. 		length--;
  70. 		heapify(a,0);
  71. 	}
  72. }
Success #stdin #stdout 0s 6804KB
comments (?)
stdin
copy 
5
1000000
3
-999999
7
1
stdout
copy 
-999999
1
3
7
1000000
https://ideone.com/sT7wdW
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!