fork download
copy 
  1. #include <algorithm>
  2. #include <limits>
  3. #include "heap.h"
  4.  
  5. int heapSize;
  6.  
  7. //Восстановление свойства кучи
  8. void heapify(int a[], int i){
  9. 	int left = 2*i;
  10. 	int right = 2*i + 1;
  11. 	//heapSize - количество элементов в куче
  12. 	int largest = i;
  13. 	if((left <= heapSize) && (a[left] > a[i]))
  14. 		largest = left;
  15. 	if((right <= heapSize) && (a[right] > a[largest]))
  16. 		largest = right;
  17. 	if(largest != i){
  18. 		std::swap(a[i], a[largest]);
  19. 		heapify(a, largest);
  20. 	}
  21. }
  22.  
  23. //перестроение в кучу массива длина size
  24. void buildHeap(int a[], int size){
  25. 	heapSize = size;
  26. 	for(int i = size/2; i >= 0; i--)
  27. 		heapify(a, i);
  28. }
  29.  
  30. //Изменение значения элемента
  31. void heapIncreaseKey(int a[], int i, int key){
  32. 	if(key < a[i])
  33. 		return;	//Ошибка
  34. 	a[i] = key;
  35. 	while((i > 0) && (a[i/2] < a[i])){
  36. 		std::swap(a[i], a[i/2]);
  37. 		i = i / 2;
  38. 	}
  39. }
  40.  
  41. //Добавление элемента
  42. void heapInsert(int a[], int key){
  43. 	heapSize = heapSize + 1;
  44. 	a[heapSize] = -INT_MAX;
  45. 	heapIncreaseKey(a, heapSize, key);
  46. }
  47.  
  48. //Извлечение максимального элемента
  49. int heapExtractMax(int a[]){
  50. 	if(heapSize < 0)
  51. 		return 0;	//Ошибка: куча пуста
  52. 	int max = a[0];
  53. 	a[0] = a[heapSize];
  54. 	heapSize = heapSize - 1;
  55. 	heapify(a, 0);
  56. 	return max;
  57. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:3:18: fatal error: heap.h: No such file or directory
 #include "heap.h"
                  ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/2GfM49
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!