vadimk772336

Untitled

Oct 28th, 2021
500
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Heap
  2. {
  3.     static const int SIZE = 100;
  4.     int* h;
  5.     int HeapSize;
  6.  
  7. public:
  8.     Heap();
  9.     void siftup();
  10.     void siftdown(int);
  11.     void add(int);
  12.     void delete_vertex(int);
  13.     bool isempty();
  14.     int* get_head();
  15.     void out();
  16. };
  17.  
  18. Heap::Heap()
  19. {
  20.  
  21.     h = new int[SIZE];
  22.     HeapSize = 0;
  23. }
  24.  
  25. int* Heap::get_head()
  26. {
  27.     return &h[0];
  28. }
  29.  
  30. bool Heap::isempty()
  31. {
  32.     if (HeapSize == 0)
  33.         return true;
  34.     return false;
  35. }
  36.  
  37. void Heap::siftup()
  38. {
  39.     int curr, parent;
  40.     curr = HeapSize - 1;
  41.     parent = (curr - 1) / 2;
  42.     while (parent >= 0 && curr > 0)
  43.     {
  44.         if (h[parent] < h[curr])
  45.         {
  46.             int buff = h[curr];
  47.             h[curr] = h[parent];
  48.             h[parent] = buff;
  49.         }
  50.         curr = parent;
  51.         parent = (curr - 1) / 2;
  52.     }
  53. }
  54.  
  55. void Heap::siftdown(int position)
  56. {
  57.     int parent, max_child;
  58.  
  59.     int curr = position;
  60.     int child_l = 2 * curr + 1;
  61.     int child_r = 2 * curr + 2;
  62.  
  63.     if (h[child_r] < h[child_l])
  64.         max_child = child_l;
  65.     else
  66.         max_child = child_r;
  67.  
  68.     while (child_l < HeapSize)
  69.     {
  70.         if (child_l == HeapSize - 1)
  71.             max_child = child_l;
  72.         else if (h[child_r] < h[child_l])
  73.             max_child = child_l;
  74.         else
  75.             max_child = child_r;
  76.  
  77.         if (h[curr] < h[max_child])
  78.         {
  79.             int buff = h[curr];
  80.             h[curr] = h[max_child];
  81.             h[max_child] = buff;
  82.         }
  83.         curr = max_child;
  84.         child_l = 2 * curr + 1;
  85.         child_r = 2 * curr + 2;
  86.     }
  87. }
  88.  
  89. void Heap::add(int vertex)
  90. {
  91.     h[HeapSize] = vertex;
  92.     HeapSize++;
  93.     siftup();
  94. }
  95.  
  96. void Heap::delete_vertex(int position)
  97. {
  98.     h[position] = h[HeapSize - 1];
  99.     HeapSize--;
  100.     siftdown(position);
  101. }
  102.  
  103. void Heap::out(void)
  104. {
  105.  
  106.     for (int i = 0; i < HeapSize; i++)
  107.     {
  108.         std::cout <<<< h[i] << "" ";
  109.    }
  110.    std::cout << std::endl;
  111. }
RAW Paste Data