Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- /**
- Implementation of an heap
- **/
- vector <int> heap;
- void insert_key ( int element );
- int father ( int i );
- int left_children ( int i );
- void decrease_key( int i, int val );
- int right_children ( int i );
- void print_heap ( void );
- void heapify ( int i );
- int main ( void )
- {
- insert_key ( 10 );
- print_heap();
- insert_key ( 20 );
- print_heap();
- insert_key ( 40 );
- print_heap();
- insert_key ( 30 );
- print_heap();
- insert_key ( 15 );
- print_heap();
- insert_key ( 50 );
- print_heap();
- insert_key ( 100 );
- print_heap();
- return 0;
- }
- void heapify ( int i ) {
- int highest = i;
- int left = left_children( i );
- int right = right_children( i );
- if ( left < heap.size() && heap [ left ] > heap [ highest ] )
- highest = left;
- if ( right < heap.size() && heap [ right ] > heap [ highest ] )
- highest = right;
- /// Current local max = heap [ highest ]
- if ( highest == i )
- return;
- swap ( heap [ i ], heap [ highest ] );
- heapify( highest );
- }
- void decrease_key( int i, int val ) {
- /// Only decrease allowed
- if ( val >= heap [ i ] ) return;
- heap [ i ] = val;
- heapify ( i );
- }
- void insert_key ( int element ) {
- int element_position = heap.size();
- heap.push_back( element );
- while ( element_position != 0 && ( heap [ element_position ] > heap [ father ( element_position ) ] ) ) {
- swap ( heap [ element_position ], heap [ father ( element_position ) ] );
- element_position = father ( element_position );
- }
- }
- int father ( int i ) { return i / 2; }
- int left_children ( int i ) { return 2 * i; }
- int right_children ( int i ) { return 2 * i + 1; }
- void print_heap ( void ) {
- cout << endl;
- for ( x : heap ) cout << x << " ";
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement