📄 pus_5295.htm
字号:
<HTML><TITLE>push_heap</TITLE><BODY>
<A HREF="ref.htm"><IMG SRC="images/banner.gif"></A>
<P><STRONG>Click on the banner to return to the Class Reference home page.</STRONG></P>
<P>©Copyright 1996 Rogue Wave Software</P>
<H2>push_heap</H2>
<HR><PRE> Algorithms</PRE><HR>
<A NAME="Summary"><H3>Summary</H3></A>
<P>Places a new element into a heap.</P>
<H3>Contents</H3>
<UL>
<A HREF="#Synopsis"><LI>Synopsis</LI></A>
<A HREF="#Description"><LI>Description</LI></A>
<A HREF="#Complexity"><LI>Complexity</LI></A>
<A HREF="#Example"><LI>Example</LI></A>
<A HREF="#Warning"><LI>Warning</LI></A>
<A HREF="#See Also"><LI>See Also</LI></A>
</UL>
<A NAME="Synopsis"><H3>Synopsis</H3></A>
<PRE>#include <algorithm></PRE>
<PRE>
template <class RandomAccessIterator>
void
<B>push_heap</B>(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
<B>push_heap</B>(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
</PRE>
<A NAME="Description"><H3>Description</H3></A>
<P>A heap is a particular organization of elements in a range between two random access iterators<SAMP> [a, b)</SAMP>. Its two key properties are:</P>
<OL><LI><P><SAMP>*a</SAMP> is the largest element in the range.</P>
</LI>
<LI><P><SAMP>*a</SAMP> may be removed by the <A HREF="pop_9596.htm"><B><I>pop_heap</B></I></A><SAMP> </SAMP>algorithm, or a new element added by the <B><I>push_heap</B></I> algorithm, in <SAMP>O(logN)</SAMP> time.</P>
</LI>
</OL>
<P>These properties make heaps useful as priority queues.</P>
<P>The <B><I>push_heap</B></I> algorithms uses the less than (<SAMP><</SAMP>) operator as the default comparison. As with all of the heap manipulation algorithms, an alternate comparison function can be specified.</P>
<P>The <B><I>push_heap</B></I> algorithm is used to add a new element to the heap. First, a new element for the heap is added to the end of a range. (For example, you can use the vector or deque member function <SAMP>push_back()</SAMP>to add the element to the end of either of those containers.) The <B><I>push_heap</B></I> algorithm assumes that the range <SAMP>[first, last - 1)</SAMP> is a valid heap. It then properly positions the element in the location <SAMP>last - 1</SAMP> into its proper position in the heap, resulting in a heap over the range <SAMP>[first, last)</SAMP>.</P>
<P>Note that the <B><I>push_heap</B></I> algorithm does not place an element into the heap's underlying container. You must user another function to add the element to the end of the container before applying <B><I>push_heap</B></I>.</P>
<A NAME="Complexity"><H3>Complexity</H3></A>
<P>For <B><I>push_heap</B></I> at most <SAMP>log(last - first)</SAMP> comparisons are performed.</P>
<A NAME="Example"><H3>Example</H3></A>
<PRE>//
// heap_ops.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
// Make heaps
make_heap(v1.begin(),v1.end());
make_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Note that x, y and z represent the remaining
// values in the container (other than 4).
// The definition of the heap and heap operations
// does not require any particular ordering
// of these values.
// Copy both vectors to cout
ostream_iterator<int> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now let's pop
pop_heap(v1.begin(),v1.end());
pop_heap(v2.begin(),v2.end(),less<int>());
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// And push
<B>push_heap</B>(v1.begin(),v1.end());
<B> push_heap</B>(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now sort those heaps
sort_heap(v1.begin(),v1.end());
sort_heap(v2.begin(),v2.end(),less<int>());
// v1 = v2 = (1,2,3,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
return 0;
}
Output :
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
</PRE>
<A NAME="Warning"><H3>Warning</H3></A>
<P>If your compiler does not support default template parameters, you need to always supply the <SAMP>Allocator</SAMP> template argument. For instance, you will need to write :</P>
<P><SAMP>vector<int, allocator></SAMP></P>
<P>instead of :</P>
<P><SAMP>vector<int></SAMP></P>
<A NAME="See Also"><H3>See Also</H3></A>
<P><A HREF="mak_0285.htm"><B><I>make_heap</B></I></A>, <A HREF="pop_9596.htm"><B><I>pop_heap</B></I></A>, <A HREF="sor_3899.htm"><B><I>sort_heap</B></I></A></P>
<HR>
<A HREF="ptr_4059.htm"><IMG SRC="images/prev.gif"></A> <A HREF="ref.htm#contents"><IMG SRC="images/toc.gif"></A> <A HREF="que_0953.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -