none
初学者请教关于push_heap和make_heap的区别问题 RRS feed

  • 问题

  • 我是C++的初学者,请教各位push_heap和make_heap有什么区别? 我查了MSDN发现他们的声明很想,看了MSDN中提供的例子就更晕了,想知道他们有什么区别和用处

    谢谢

    2008年11月17日 13:47

答案

  • 简单地说,make_heap就是把转换范围内的所有数按照堆的要求进行重排;而push_heap是把一个数添加到排列好的堆中。

     

    The make_heap function converts the range [first..last) into a heap.

    The sort_heap function sorts a "heapified" sequence that was created using the make_heap function.

    The push_heap function inserts a new value into the heap.

    The pop_heap function swaps the first and last elements in the heap specified by [first, last), then reduces the length of the sequence by one before restoring the heap property.

     

    Code Snippet

    Sample Code
    //////////////////////////////////////////////////////////////////////
    //
    // Compile options needed: /GX
    //
    // heap_functions.cpp : Illustrates how to use the predicate versions
    //                      of the make_heap, sort_heap, push_heap
    //                      and pop_heap functions.
    //
    // Functions:
    //
    //    make_heap : Convert a sequence to a heap.
    //    sort_heap : Sort a heap.
    //    push_heap : Insert an element in a heap.
    //    pop_heap  : Remove the top element from a heap.
    //
    // Written by Kalindi Sanghrajka
    // of Microsoft Product Support Services,
    // Software Core Developer Support.
    // Copyright (c) 1996 Microsoft Corporation. All rights reserved.
    ////////////////////////////////////////////////////////////////////// 

    // disable warning C4786: symbol greater than 255 character,
    // okay to ignore
    #pragma warning(disable: 4786)

    #include <iostream>
    #include <algorithm>
    #include <functional>
    #include <vector>
    using namespace std;

    void main()
    {
       const int VECTOR_SIZE = 8 ;

       // Define a template class vector of int
       typedef vector<int, allocator<int> > IntVector ;

       //Define an iterator for template class vector of strings
       typedef IntVector::iterator IntVectorIt ;

       IntVector Numbers(VECTOR_SIZE) ;
       IntVectorIt it ;

       // Initialize vector Numbers
       Numbers[0] = 4 ;
       Numbers[1] = 10;

       Numbers[2] = 70 ;
       Numbers[3] = 10 ;
       Numbers[4] = 30 ;
       Numbers[5] = 69 ;
       Numbers[6] = 96 ;
       Numbers[7] = 100;

       // print content of Numbers
       cout << "Numbers { " ;
       for(it = Numbers.begin(); it != Numbers.end(); it++)
          cout << *it << " " ;
       cout << " }\n" << endl ;

       // convert Numbers into a heap
       make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
       cout << "After calling make_heap\n" << endl ;

       // print content of Numbers
       cout << "Numbers { " ;
       for(it = Numbers.begin(); it != Numbers.end(); it++)
          cout << *it << " " ;
       cout << " }\n" << endl ;

       // sort the heapified sequence Numbers
       sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
       cout << "After calling sort_heap\n" << endl ;

       // print content of Numbers
       cout << "Numbers { " ;
       for(it = Numbers.begin(); it != Numbers.end(); it++)
          cout << *it << " " ;
       cout << " }\n" << endl ;

       make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
       //insert an element in the heap
       Numbers.push_back(7) ;
       push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
       cout << "After calling push_heap()\n" << endl;

       // print content of Numbers
       cout << "Numbers { " ;
       for(it = Numbers.begin(); it != Numbers.end(); it++)
          cout << *it << " " ;
       cout << " }\n" << endl ;

       //remove the root element from the heap Numbers
       pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
       cout << "After calling pop_heap\n" << endl ;

       // print content of Numbers
       cout << "Numbers { " ;
       for(it = Numbers.begin(); it != Numbers.end(); it++)
          cout << *it << " " ;
       cout << " }\n" << endl ;

     

     

    Program Output is:

    Numbers { 4 10 70 10 30 69 96 100  }
        
    After calling make_heap

    Numbers { 4 10 69 10 30 70 96 100  }
        
    After calling sort_heap

    Numbers { 100 96 70 69 30 10 10 4  }
        
    After calling push_heap()

    Numbers { 4 7 10 30 100 10 70 96 69  }
        
    After calling pop_heap

    Numbers { 7 30 10 69 100 10 70 96 4  }

     

    				
    2008年11月21日 7:01