Cette page vous a-t-elle été utile ?
Votre avis sur ce contenu est important. N'hésitez pas à nous faire part de vos commentaires.
Vous avez d'autres commentaires ?
1500 caractères restants
Exporter (0) Imprimer
Développer tout
Développer Réduire
Important Il est possible que le présent document ne corresponde pas aux pratiques recommandées pour le développement actuel. Par ailleurs, il se peut que des liens de téléchargement et d'autres ressources ne soient plus valides. La version recommandée actuelle est disponible ici.

heap

Illustrates how to use the heap Standard Template Library (STL) functions in Visual C++.


template<class RandomAccessIterator> inline
   void make_heap(
      RandomAccessIterator First,
      RandomAccessIterator Last
   )
template<class RandomAccessIterator> inline
   void sort_heap(
      RandomAccessIterator First,
      RandomAccessIterator Last
   )
template<class RandomAccessIterator> inline
   void push_heap(
      RandomAccessIterator First,
      RandomAccessIterator Last
   )
template<class RandomAccessIterator> inline
   void pop_heap(
      RandomAccessIterator First,
      RandomAccessIterator Last
   )

Note Note:

The class/parameter names in the prototype do not match the version in the header file. Some have been modified to improve readability.

A heap is a sequence of elements organized like a binary tree. Each heap element corresponds to a tree node. The first value in the sequence [First..Last) is the root and is the largest value in the heap. Every element in the heap satisfies the following: Every element is less than or equal to its parent. The largest element is stored in the root, and all children hold progressively smaller values. The make_heap function converts the range [First..Last) into a heap. The sort_heap function sorts a 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), and then reduces the length of the sequence by one before restoring the heap property. The nonpredicate versions of the heap functions use operator< for comparisons.

// heapfunc.cpp
// compile with: /EHsc
// 
// 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

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

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

int main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<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()) ;

    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()) ;

    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 ;

    //insert an element in the heap
    Numbers.push_back(7) ;
    push_heap(Numbers.begin(), Numbers.end()) ;

    // you need to call make_heap to re-assert the
    // heap property
    make_heap(Numbers.begin(), Numbers.end()) ;

    cout << "After calling push_heap and make_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()) ;

    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 ;
}

Numbers { 4 10 70 10 30 69 96 100  }

After calling make_heap

Numbers { 100 30 96 10 4 69 70 10  }

After calling sort_heap

Numbers { 4 10 10 30 69 70 96 100  }

After calling push_heap and make_heap

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

After calling pop_heap

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

Header: <algorithm>

Ajouts de la communauté

AJOUTER
Microsoft réalise une enquête en ligne pour recueillir votre opinion sur le site Web de MSDN. Si vous choisissez d’y participer, cette enquête en ligne vous sera présentée lorsque vous quitterez le site Web de MSDN.

Si vous souhaitez y participer,
Afficher:
© 2015 Microsoft