Advertisement
DimasDark

Heap ~C++

Aug 11th, 2013
267
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <iterator>
  4.  
  5. using namespace std;
  6.  
  7. class Heap {
  8. public:
  9.     Heap();
  10.     ~Heap();
  11.     void insert(int element);
  12.     int deletemin();
  13.     void print();
  14.     int size() { return heap.size(); }
  15. private:
  16.     int left(int parent);
  17.     int right(int parent);
  18.     int parent(int child);
  19.     void heapifyup(int index);
  20.     void heapifydown(int index);
  21. private:
  22.     vector<int> heap;
  23. };
  24.  
  25. Heap::Heap()
  26. {
  27. }
  28.  
  29. Heap::~Heap()
  30. {
  31. }
  32.  
  33. void Heap::insert(int element)
  34. {
  35.     heap.push_back(element);
  36.     heapifyup(heap.size() - 1);
  37. }
  38.  
  39. int Heap::deletemin()
  40. {
  41.     int min = heap.front();
  42.     heap[0] = heap.at(heap.size() - 1);
  43.     heap.pop_back();
  44.     heapifydown(0);
  45.     return min;
  46. }
  47.  
  48. void Heap::print()
  49. {
  50.     vector<int>::iterator pos = heap.begin();
  51.     cout << "Heap = ";
  52.     while ( pos != heap.end() ) {
  53.         cout << *pos << " ";
  54.         ++pos;
  55.     }
  56.     cout << endl;
  57. }
  58.  
  59. void Heap::heapifyup(int index)
  60. {
  61.     //cout << "index=" << index << endl;
  62.     //cout << "parent(index)=" << parent(index) << endl;
  63.     //cout << "heap[parent(index)]=" << heap[parent(index)] << endl;
  64.     //cout << "heap[index]=" << heap[index] << endl;
  65.     while ( ( index > 0 ) && ( parent(index) >= 0 ) &&
  66.             ( heap[parent(index)] > heap[index] ) )
  67.     {
  68.         int tmp = heap[parent(index)];
  69.         heap[parent(index)] = heap[index];
  70.         heap[index] = tmp;
  71.         index = parent(index);
  72.     }
  73. }
  74.  
  75. void Heap::heapifydown(int index)
  76. {
  77.     //cout << "index=" << index << endl;
  78.     //cout << "left(index)=" << left(index) << endl;
  79.     //cout << "right(index)=" << right(index) << endl;
  80.     int child = left(index);
  81.     if ( ( child > 0 ) && ( right(index) > 0 ) &&
  82.          ( heap[child] > heap[right(index)] ) )
  83.     {
  84.         child = right(index);
  85.     }
  86.     if ( child > 0 )
  87.     {
  88.         int tmp = heap[index];
  89.         heap[index] = heap[child];
  90.         heap[child] = tmp;
  91.         heapifydown(child);
  92.     }
  93. }
  94.  
  95. int Heap::left(int parent)
  96. {
  97.     int i = ( parent << 1 ) + 1; // 2 * parent + 1
  98.     return ( i < heap.size() ) ? i : -1;
  99. }
  100.  
  101. int Heap::right(int parent)
  102. {
  103.     int i = ( parent << 1 ) + 2; // 2 * parent + 2
  104.     return ( i < heap.size() ) ? i : -1;
  105. }
  106.  
  107. int Heap::parent(int child)
  108. {
  109.     if (child != 0)
  110.     {
  111.         int i = (child - 1) >> 1;
  112.         return i;
  113.     }
  114.     return -1;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement