<> Complete binary reactor
Heap can also be called complete binary heap . This is logically based on a complete binary tree , Physically, it is generally based on linear data structure （ Such as array , vector , Linked list, etc ） A data structure for .
<> Storage structure of complete binary tree
Students who have studied complete binary trees should understand , A complete binary tree can be physically represented by a linear data structure （ Or store ）, For example, array int a[5] =
{1,2,3,4,5} Can be used to describe a person who has 5 Complete binary tree of nodes . Then the heap structure based on complete binary tree can also be described by linear structure . Look back on this expression , The relationship between the rank of elements . If there are elements, the rank is k(k
>= 0), Then there Rank(LeftChild) = 2k+1,Rank(RightChild) = 2
k+2（ Here the rank of the element is from 0 start , If from 1 At the beginning, the derived formula is slightly different , Notice the difference ）.
<> Heap ordering
Heaps can be divided into two types ： Big root pile （ Maximum heap ）, Small root pile （ Minimum heap ）.
<> Big root pile
What is big root pile ? seeing the name of a thing one thinks of its function , Large root heap refers to the logical binary tree structure , Root node > Child node , Always the biggest , And this is true in every part of the heap
. for example {3,1,2} It can be seen as a large root pile , and {3,2,1} It can also be regarded as a large root pile . The root node of the large root heap is the largest element in the whole heap .
<> Small root pile
The nature of small root pile is similar to that of large root pile , It's just in the structure of a binary tree , Root node < Child node . for example {1,2,3} Small root pile ,{1,3,2} It is also a small root pile . The root node of the small root heap is the smallest element in the whole heap .
<> Summary
* large / The root node in the small root heap is the largest in the whole sequence / Small element , Then get the maximum from the heap / Small elements are very fast , Just return the first element in the sequence .
* More general , Local ordering of heap , The order of the whole heap is formed . As long as there is a local failure to meet the order of the heap , It can be said that the heap is out of order , At this time, corresponding adjustment is required .
<> Common scenarios for heap
1, According to the previous summary , We can use the nature of the heap to find the largest in a sequence / Small element , This is a method , Although it may be better to solve this problem by traversal .
2, Heap sort , I believe that students who have studied heap sorting will agree with this .
3, Establish priority queue , According to the above summary , If heap is used to establish priority queue , You can quickly get the highest priority in the queue / Low task .
4,n The first elements are arranged k Big element problem , For such problems , You can build a small root heap , Read in sequence n Multiple elements and adjust , And the scale of the reactor reaches k+1 Time , Eliminate the second 1 Elements , be left over k Larger elements , Keep the size of the heap no more than k, Keep cycling to get the final result .
5, For other applications, please leave a message for guidance , Discuss each other , Thank you very much .
<> Heap operation
What about the operation of the heap , Nothing more than building , insert , delete . Creating an empty heap is a very simple operation , It is worth thinking about how to use an existing sequence to generate one ; Insert and delete operations , Relatively simple ; It is worth thinking about how to restore the heap order after inserting or deleting elements .
<> Insertion and upfiltration of reactor
* Inserting an element into a linear sequence is relatively simple , For example, array a[N], At rank k(k<N) Insert an element at the location of e, It is divided into the following operations ：a)
Rank greater than or equal to k The element of is moved back one bit at a time ;b) take a[k] Assign as e.
* Suppose the heap uses an array as the underlying implementation , So how to implement heap insertion ? Is inserted into the head of the original heap ? Or tail ? Or in the middle ?
Since the original heap has maintained heap order , If inserted in the head , The parent and child nodes corresponding to all elements will change , This will cause the entire heap to fail ; If it is inserted at a certain position in the middle , The parent and child nodes corresponding to all elements after the insertion position will be changed , This will result in partial failure of the heap ; If inserted at the bottom of the heap , The structure of the original reactor is not damaged , At this point, the only thing that may not conform to the nature of the heap is the last element （ Element just inserted ） Is the parent node larger than it / Small , That is, whether this part still satisfies the previously mentioned heap ordering .
*
good , Now? , You can determine that the cost of inserting a new element at the bottom of the heap is minimal , The next step is to think about how to restore heap ordering in this case . Imagine a small root pile as follows {2,3}, Insert an element at its tail 1, How to adjust it to meet the properties of small root heap ? yes , By placing elements 2 And elements 1 Exchange to get the small root heap {1,3,2}. At this time, it is not difficult to see the nature of the following small root piles , In this case , You can restore the heap order by performing the following operations on the out of order heap ： If the newly inserted node is smaller than its parent node , Then exchange the two .
*
In the case described in Article 3 , There is no sibling node for the newly inserted node （ If any ） Do anything , You don't even need to think about it , Why ? Assume that the newly inserted node is N, Its parent node is F(N), Its sibling node is B(N), In the original pile （ node N Before insertion ） There is such a relationship in ：F(N)
< B(N). Insert Knot N after , if N < F(N), Then there N < F(N) < B(N). Review the description of heap ordering , It's not hard to know, as long as N And F(N) Swapping positions can restore heap order .
*
From point to surface , Assume the above heap {2,3} Just another pile heap2 Local in （3 by heap2 Bottom of heap element in ,2 by 3 Parent node of ）, Through the operation described in the previous article , We can restore local heap ordering , But don't forget , Due to the original element 2 Becomes an element 1, Continue checking the element at this time 1 And elements 1 Parent node of , Does the local heap composed of sibling nodes satisfy heap ordering , Cycle back and forth until the part where the inserted element is located satisfies heap ordering . Such a process is also called
Upper filtration of reactor （percolateUp）.
The code is as follows ： template<typename T> void percolateUp(T *s, size_t rank) { while(rank) {
size_t f= (rank-1)>>1; if (s[f] > s[rank]) { swap(s[f], s[rank]); rank = f; }
else break; } }
* Time complexity ,O(logn). It is not difficult to see that the inserted nodes rise layer by layer （ Exchange position with parent node ）, The height of a complete binary tree is logn, Therefore, the time complexity is O(logn).
<> Deletion and down filtering of heap
*
It is simple to delete an element from a linear sequence , But for a structure like a heap , There is no point in deleting an element by comparison , The order of the heap tells us , It is valuable to remove the top element from the heap （ Time complexity O(1)）. You might as well treat the deletion of the heap as taking out the top element of the heap .
*
For a heap heap for , To remove the top element, just delete it heap[0] that will do , So after deleting the first element , The original heap lost its heel node , The whole heap is facing the embarrassment of failure . Similar to the insert operation , Need to think about a problem , How to adjust the original structure that can keep other parts of the original heap （ Parent child relationship between elements ）? You can insert another element at the position of the deleted first element to keep the structure of other nodes in the original heap unchanged , This process can be regarded as a new node replacing the original root node .
*
So where does this new node come from ? If a node in the middle is selected X To replace the root node , Will cause X All subsequent nodes fail （ The original structure was destroyed ）. thus , I believe it is not difficult to see , Just like the insert operation , It is the best choice to select the bottom element to replace the root node , This allows the whole heap to maintain its original structure . The next thing to consider is whether the whole heap still maintains heap order after replacement .
*
As mentioned earlier, the local order of the heap is the overall order of the heap , So after the replacement , The local order becomes the basis for judging the overall order of the reactor . Use separately N,L(N),R(N) Represents the root node after replacement , Left child of root node , Right child of root node . If N
< L(N) And N < R(N), Then the heap order remains ; Otherwise, the heap order is destroyed . It is better to write the above conditions in the following form ： If N < MIN(L(N),
R(N)), Then the heap order remains ; Otherwise, the heap order is destroyed . This situation is slightly different from the sequential failure caused by inserting an element at the bottom of the heap , The next thing to think about is how to adjust to restore the local order of the heap ? Can we solve this kind of disorder by a scheme similar to up filtering ?
*
Let's go back to the feature of heap ordering , about N,L(N),R(N) For the local heap composed of these three nodes , The heap ordering can be maintained by ensuring that the minimum of the three is at the root node . thus , It can be concluded that if N
< MIN(L(N), R(N)) Not satisfied , Will N And MIN(L(N),
R(N)) Call the location to maintain heap order . Same as insertion processing , After one adjustment, it is necessary to continue to adjust the newly formed local heap , move in circles , Until the local heap recovers the heap order or node N Become a leaf node . Such a process is also called
Downfiltration of reactor （percolateDown）.
The code is as follows ： template<typanme T> void percolateDown(T *s, size_t rank, size_t size) {
size_t lastInternal= (size-1)/2; // Rank of the last internal node while (rank < lastInternal) {
size_t lChild= rank*2+1; // Left child's rank size_t rChild = rank*2+2; // Rank of right child size_t LChild
= s[lChild] < s[rChild] ? lChild : rChild; // The smallest of the child nodes can become the parent node if (s[lChild] < s[
rank]) // If heap ordering is violated { swap(s[LChild], s[rank]); // exchange rank = LChild; // Continue to investigate } else
break; } if (rank == lastInternal) // If it is adjusted to the last internal node , You need to judge whether there is a right child { size_t lChild
= rank*2+1; size_t rChild = rank*2+2; size_t LChild = s[lChild] < s[rChild] ?
lChild: rChild; if (rChild == size) // Right child cross the border LChild = lChild; else LChild = s[
lChild] < s[rChild] ? lChild : rChild; if (s[LChild] < s[rank]) swap(s[Lchild],
s[rank]); } }
* Time complexity , In a progressive sense O(logn), Its internal operation is more than that of the upper filtration process , Therefore, the constant coefficient is slightly higher .
<> Build a heap using an existing sequence
*
This problem can be solved by creating an empty heap , Then insert the elements in the sequence into the heap one by one , It can be roughly concluded that the time complexity is O(nlogn). If such operation is carried out in situ , It is equivalent to performing up filtering from the first element to the last element in turn , For the time being, this method is called top-down top filtering .
* Can I use down filtering to achieve this function ? Start with the last internal node , Filter down all internal nodes one by one , After that, you can get a heap .
*
Here , The process of filtering down the internal node can be regarded as the process of merging the internal node and its left and right sub heaps into one heap . Set internal node as N, The left and right sub stacks are used respectively HL and HR To represent . Both heap , that HL And HR Both meet heap ordering , In fact, when starting from the last internal node ,HL And HR Each contains at most one element , A heap with only one element is naturally ordered . Wait until the parent nodes of all leaf nodes are stacked with their left and right children （ There is only one element in the heap ） After merger , Will appear HL and HR Contains multiple elements , The sub stacks adjusted by down filtering meet the heap order . So far, it can be proved that the order of the whole heap can be restored in this way . We might as well call this method bottom-up filtering .
*
The time complexity is O(n), Yes, it may not be consistent with everyone's intuitive feeling , The proof process requires induction , It won't go on here . However, it can be simply compared with the top-down filtering algorithm ： First, the filter up operation needs to be performed on all elements , And the closer to the bottom of the heap, the more elements may need to be exchanged , This means that there may be more elements that need to be exchanged more times ; The down filtration reactor only needs to perform the down filtration operation on all internal nodes , This is half the number of elements in the operation , Secondly, the closer the internal nodes to the bottom of the heap, the less the number of exchanges required , This means that most internal nodes only need to perform fewer exchanges , Only the elements closer to the top of the heap need more exchange , And the closer we get to the top of the pile , The fewer elements . It can be seen that the bottom-up filtering heap building algorithm is better than the top-down filtering algorithm in the progressive sense of time complexity . In fact, the bottom-up heap building algorithm is called
Floyd pile building method .
The code is as follows template<typename T> void heapify(T *s, size_t size) { int rank; auto
getLastInternal= [size] {return (size-1)>>1;}; if ((rank = getLastInternal()) <
0) // Get the last internal node return ; while (rank>= 0) // Filter down each internal node { percolateDown(s, rank,
size); --rank; } }
Record the learning process , If all gods have advice , Can leave a message to discuss , be deeply grateful !
Technology
Daily Recommendation