Advertisement
informaticage

Heap implementation OII

Oct 24th, 2019
319
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. /**
  8.     Implementation of an heap
  9. **/
  10. vector <int> heap;
  11.  
  12. void insert_key ( int element );
  13. int father ( int i );
  14. int left_children ( int i );
  15. void decrease_key( int i, int val );
  16. int right_children ( int i );
  17. void print_heap ( void );
  18. void heapify ( int i );
  19.  
  20. int main ( void )
  21. {
  22.     insert_key ( 10 );
  23.     print_heap();
  24.     insert_key ( 20 );
  25.     print_heap();
  26.     insert_key ( 40 );
  27.     print_heap();
  28.     insert_key ( 30 );
  29.     print_heap();
  30.     insert_key ( 15 );
  31.     print_heap();
  32.     insert_key ( 50 );
  33.     print_heap();
  34.     insert_key ( 100 );
  35.     print_heap();
  36.  
  37.     return 0;
  38. }
  39.  
  40. void heapify ( int i ) {
  41.     int highest = i;
  42.     int left = left_children( i );
  43.     int right = right_children( i );
  44.  
  45.     if ( left < heap.size() && heap [ left ] > heap [ highest ] )
  46.         highest = left;
  47.  
  48.     if ( right < heap.size() && heap [ right ] > heap [ highest ] )
  49.         highest = right;
  50.  
  51.     /// Current local max = heap [ highest ]
  52.     if ( highest == i )
  53.         return;
  54.  
  55.     swap ( heap [ i ], heap [ highest ] );
  56.     heapify( highest );
  57. }
  58.  
  59. void decrease_key( int i, int val ) {
  60.     /// Only decrease allowed
  61.     if ( val >= heap [ i ] ) return;
  62.  
  63.     heap [ i ] = val;
  64.     heapify ( i );
  65. }
  66.  
  67. void insert_key ( int element ) {
  68.     int element_position = heap.size();
  69.     heap.push_back( element );
  70.  
  71.     while ( element_position != 0 && ( heap [ element_position ] > heap [ father ( element_position ) ] ) ) {
  72.         swap ( heap [ element_position ],  heap [ father ( element_position ) ] );
  73.         element_position = father ( element_position );
  74.     }
  75. }
  76.  
  77. int father ( int i ) { return i / 2; }
  78. int left_children ( int i ) { return 2 * i; }
  79. int right_children ( int i ) { return 2 * i + 1; }
  80.  
  81. void print_heap ( void ) {
  82.     cout << endl;
  83.     for ( x : heap ) cout << x << " ";
  84.     cout << endl;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement