STL Source Analysis - Sequential Container#5 heap

Heap is not exactly a STL container, but it is an essential part of one of the container priority queues.As the name implies, priority queue is a priority queue that allows the user to add any element to the container in any order, but it begins with the element with the highest priority.There are two kinds of priority, which can be the lowest or highest value in the container.Priority queue is the criterion by which the high value is chosen as the priority.The corresponding implementation is binary max heap, which acts as the underlying mechanism of priority queue.

The so-called binary heap (binary heap) is a complete binary tree, that is, the whole binary tree is full except for the bottom leaf nodes, and the bottom node must not have empty nodes from left to right, as shown in the figure:



As shown in the diagram, there are no node holes in the whole tree of a complete binary tree, which allows us to use arrays to store all the nodes in a complete binary tree.In addition, if index 1 of our array begins to record nodes, the relationship between parent and child nodes in the array is generally as follows: parent node at i, left child node at 2I of the array, and right child node at 2i+1 of the array.This representation of trees as arrays is called implicit representation.Our heap needs to dynamically change the number of nodes, so vector s are a better choice.Since priority queue chooses binary max heap as its underlying mechanism, only the implementation of Max heap is provided, so what we will discuss next is the max heap.Each node's key value is greater than or equal to the key value of its child nodes.


heap algorithm

  • push_heap

In order to satisfy the condition of a complete binary tree, the newly added elements must be placed at the bottom level as leaf nodes and filled in the first space from left to right.Newly added elements are not necessarily suitable for existing locations. In order to satisfy the max-heap criteria, we need to perform a percolate up operation on newly added elements: compare the new node with its parent node, if its key value is larger than the parent node, the parent and child exchange locations, then the new element added after the exchange becomes the parent node, and then compare with its parent node.This continues upstream until there is no need to swap or until the root node.



The push_heap function accepts two random iterators to represent the end and end of a heap's bottom container, and new elements are inserted at the end of the bottom container before they enter the function.If the parameters do not match, or if no new elements are inserted, the function will not perform as expected.

 1 template <class RandomAccessIterator>
 2 inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
 3     // Note that when this function is called, the new element should have been placed at the end of the underlying container.
 4     //The function is called only after a new element is added to the array (next to the original last element)
 5     __push_heap_aux(first, last, distance_type(first), value_type(first));
 6 }
7 template <class RandomAccessIterator, class Distance, class T> 8 inline void __push_heap_aux(RandomAccessIterator first, 9 RandomAccessIterator last, Distance*, T*) { 10 __push_heap(first, Distance((last - first) - 1), Distance(0), 11 T(*(last - 1))); 12 //Object type referred to by iterator obtained from last function T,For cast 13 //Distance(0)Index value to indicate maximum value 14 //Distance((last - first) - 1)Index value to indicate new value added 15 }
16 template <class RandomAccessIterator, class Distance, class T> 17 void __push_heap(RandomAccessIterator first, Distance holeIndex, 18 Distance topIndex, T value) { 19 //holeIndex Index value to indicate new value added 20 //topIndex Maximum Index Value 21 //value Add value to new content 22 Distance parent = (holeIndex - 1) / 2; // Find the parent node of the new element 23 while (holeIndex > topIndex && *(first + parent) < value) { 24 // When the top has not been reached and the parent node is less than the new value (does not match) heap Order feature), continue to float up 25 // Because of the above use operator<,knowable STL heap Is a max-heap(Big root heap). 26 *(first + holeIndex) = *(first + parent); // Child Position Set Parent Value 27 holeIndex = parent; // percolate up: Adjust the index value of the newly added value to promote up to the parent node. 28 parent = (holeIndex - 1) / 2; // Parent node to get new index value 29 } // Continue to the top, or satisfy heap Until the order property of. 30 *(first + holeIndex) = value; // Complete the insertion by making the final index value a new value. 31 }
  • pop_heap

The maximum value is at the root node, and the pop operation takes the root node (actually transfers it to the end node of the vector s). In order to satisfy the condition of a complete binary tree, the bottom-most and right-most node must be cut off, its value taken out into a temporary variable, and then the value of the root node (which will eventually be removed by pop_back()) at that location.

 1 template <class RandomAccessIterator>
 2 inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
 3     __pop_heap_aux(first, last, value_type(first));
 4 }
 6 template <class RandomAccessIterator, class T>
 7 inline void __pop_heap_aux(RandomAccessIterator first,
 8     RandomAccessIterator last, T*) {
 9     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
10     // Set the end value of the alignment bar adjustment, and then set the first value to
11     // End node (so the above iterator result Set to last-1). Then reorganize [first, last-1),
12     // Make it eligible again heap. 
13 }
15 template <class RandomAccessIterator, class T, class Distance>
16 inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
17     RandomAccessIterator result, T value, Distance*) {
18     *result = *first; // Set the tail value to be the first value so that the tail value is the desired result.
19                       // Can be called later by the client pop_back() Take out the tail value.
20     __adjust_heap(first, Distance(0), Distance(last - first), value);
21     // Above readjustment heap,The index value to be adjusted is 0 (that is, at the root of the tree), and the index value to be adjusted is 0 value(Original tail value).
22 }
24 template <class RandomAccessIterator, class Distance, class T>
25 void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
26     Distance len, T value) {
27     //holeIndex: To adjust the index value, start at the root of the tree
28     //len: The number of elements (excluding the first node adjusted to the tail node), that is[0, len)
29     //value: Recorded the value of the original bottom-most right-most node
30     Distance topIndex = holeIndex;
31     Distance secondChild = 2 * holeIndex + 2; // Right child node of adjusted index value
32     while (secondChild < len) {
33         // Compare the left and right subvalues, and then use the secondChild Represents a larger child node.
34         if (*(first + secondChild) < *(first + (secondChild - 1)))
35             secondChild--;
36         // Percolate down: Replace the value at the index value with a larger subvalue, and move the adjusted index value down to the larger subnode.
37         *(first + holeIndex) = *(first + secondChild);
38         holeIndex = secondChild;
39         // Continue to find the right child of the index value to adjust
40         secondChild = 2 * (secondChild + 1);
41     }
42     if (secondChild == len) { // Equal, indicating that there is no right child node (not no, but prepared) pop Missing elements occupied, see*result = *first;),Only left child nodes
43                               // Percolate down: Replace the value at the index value with the left subvalue, and move the index value down to the left subnode.
44         *(first + holeIndex) = *(first + (secondChild - 1));
45         holeIndex = secondChild - 1;
46     }
48     // The order feature may not be satisfied at this point, so perform another float operation
49     __push_heap(first, holeIndex, topIndex, value);
50 }

Note that after pop_heap, the largest element is only placed at the end of the bottom container and has not been removed.To get its value, use the back() function of the bottom container.If you want to remove it, use the pop_back() function provided by the bottom container.

  • sort_heap

Since each call to pop_heap yields the element with the largest key value in the heap, if the pop_heap operation is continued on the entire heap and the scope of each operation is reduced by one element from the back to the front, then when the entire program is finished, we have an incremental sequence.sort_heap does just that.This function accepts two iterators to represent the beginning and end of the heap.If it is not the beginning or end, the result of the function is unexpected.Note that after sorting, the bottom container is no longer a legal heap.

1 template <class RandomAccessIterator>
2 void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
3     // Following, once per execution pop_heap(),The maximum is placed at the end.
4     // Execute the end minus (one space to the left) again pop_heap(),The subextreme is placed at the new end.Keep going and you'll get it in the end
5     // Sort results.
6     while (last - first > 1)
7         pop_heap(first, last--); // Per Execution pop_heap() Once, the operation range is retracted one space.
8 }


  • make_heap

This algorithm converts an existing piece of data into a heap.The key to converting a piece of data into a heap is to find the last node that has a child node, for example:


Assuming that this is a normal array and has no heap attribute, to convert it to a heap, the starting point is to find the last node with a child node. In the figure above, point E is the sub-tree headed by the E node, which sinks and floats by exchanging the values of E and J before floating J.The subtree headed by the E node is heap-compliant.Then the auto-decrement arrives at the D node (the second node with children), and the sub-tree headed by the D node sinks and floats, then auto-decreases until the root node is reached.This makes the entire array heap-compliant.So here comes the question...?How do I find the index value of the last node with a child node in a normal array?It can be demonstrated that if there is an array of length n, then the index value of the last node with a child node is (n - 2) / 2, which is when the array starts with index 0.

 1 // take [first,last) Arrange as one heap. 
 2 template <class RandomAccessIterator>
 3 inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
 4     __make_heap(first, last, value_type(first), distance_type(first));
 5 }
 7 template <class RandomAccessIterator, class T, class Distance>
 8 void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
 9     Distance*) {
10     if (last - first < 2) return; // If the length is 0 or 1, you do not have to rearrange it.
11     Distance len = last - first;
12     // Find the first subtree head that needs to be rearranged to parent Indicate.Since no leaf node needs to be executed
13         // perlocate down(Sink), so here's the calculation.
14         Distance parent = (len - 2) / 2;
16     while (true) {
17         // Rearrange to parent Is the first subtree. len Is to allow __adjust_heap() Judging Operational Scope
18         __adjust_heap(first, parent, len, T(*(first + parent)));
19         if (parent == 0) return; // Until the root node, it ends.
20         parent--; // Before the root node, move the index value (of the sub-tree to be rearranged) forward one node
21     }
22 }

Heap does not have an iterator, and all elements of a heap must follow special permutation rules, so heap does not provide traversal or iterators.

Tags: C++ less Attribute

Posted on Thu, 07 Nov 2019 04:45:04 -0800 by martin_g