📄 hea_8081.htm
字号:
<HTML><HEAD><TITLE>14.8 Heap Operations</TITLE></HEAD><BODY><A HREF="ug1.htm"><IMG SRC="images/banner.gif"></A><BR><A HREF="set_1753.htm"><IMG SRC="images/prev.gif"></A><A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="usi_0776.htm"><IMG SRC="images/next.gif"></A><BR><STRONG>Click on the banner to return to the user guide home page.</STRONG><H2>14.8 Heap Operations</H2><A NAME="idx178"><!></A><P>A <I>heap</I> is a binary tree in which every node is larger than the values associated with either child. A heap (and, for that matter, a binary tree) can be very efficiently stored in a vector, by placing the children of node<SAMP> i</SAMP> in positions <SAMP>2 * i + 1</SAMP> and <SAMP>2 * i + 2</SAMP>.</P><P>Using this encoding, the largest value in the heap will always be located in the initial position, and can therefore be very efficiently retrieved. In addition, efficient (logarithmic) algorithms exist that both permit a new element to be added to a heap and the largest element removed from a heap. For these reasons, a heap is a natural representation for the <A HREF="../stdlibcr/pri_2327.htm"><B><I>priority_queue</I></B></A> data type, described in <A HREF="pri_2327.htm">Section 11.</A></P><P>The default operator is the less-than operator (operator <SAMP><</SAMP>) appropriate to the element type. If desired, an alternative operator can be specified. For example, by using the greater-than operator (operator <SAMP>></SAMP>), one can construct a heap that will locate the smallest element in the first location, instead of the largest.</P><A HREF="sidebar1.htm#sidebar75"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Heaps and Ordered Collections</STRONG></A><A NAME="idx179"><!></A><P>The algorithm <SAMP>make_heap()</SAMP> takes a range, specified by random access iterators, and converts it into a heap. The number of steps required is a linear function of the number of elements in the range.</P><PRE>void make_heap (RandomAccessIterator first, RandomAccessIterator last [, Compare ]);</PRE><A NAME="idx180"><!></A><P>A new element is added to a heap by inserting it at the end of a range (using the <SAMP>push_back()</SAMP> member function of a vector or deque, for example), followed by an invocation of the algorithm <SAMP>push_heap().</SAMP> The <SAMP>push_heap()</SAMP> algorithm restores the heap property, performing at most a logarithmic number of operations.</P><PRE>void push_heap (RandomAccessIterator first, RandomAccessIterator last [, Compare ]);</PRE><A NAME="idx181"><!></A><P>The algorithm <SAMP>pop_heap()</SAMP> swaps the first and final elements in a range, then restores to a heap the collection without the final element. The largest value of the original collection is therefore still available as the last element in the range (accessible, for example, using the <SAMP>back()</SAMP> member function in a vector, and removable using the <SAMP>pop_back()</SAMP> member function), while the remainder of the collection continues to have the heap property. The <SAMP>pop_heap()</SAMP> algorithm performs at most a logarithmic number of operations.</P><PRE>void pop_heap (RandomAccessIterator first, RandomAccessIterator last [, Compare ]);</PRE><A NAME="idx182"><!></A><P>Finally, the algorithm <SAMP>sort_heap()</SAMP> converts a heap into a ordered (sorted) collection. Note that a sorted collection is still a heap, although the reverse is not the case. The sort is performed using approximately <SAMP>n log n</SAMP> operations, where <SAMP>n</SAMP> represents the number of elements in the range. The <SAMP>sort_heap()</SAMP> algorithm is not stable.</P><PRE>void sort_heap (RandomAccessIterator first, RandomAccessIterator last [, Compare ]);</PRE><P>Here is an example program that illustrates the use of these functions.</P><PRE>void heap_example () // illustrate the use of the heap algorithms{ // make a heap of 15 random integers vector<int> aVec(15); generate (aVec.begin(), aVec.end(), randomValue); make_heap (aVec.begin(), aVec.end()); cout << "Largest value " << aVec.front() << endl; // remove largest and reheap pop_heap (aVec.begin(), aVec.end()); aVec.pop_back(); // add a 97 to the heap aVec.push_back (97); push_heap (aVec.begin(), aVec.end()); // finally, make into a sorted collection sort_heap (aVec.begin(), aVec.end());}</PRE><BR><HR><A HREF="set_1753.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="usi_0776.htm"><IMG SRC="images/next.gif"></A><P>©Copyright 1996, Rogue Wave Software, Inc.</P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -