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/JuoxtN
language:
C++ (gcc 8.3)
created:
11 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!