Simulated small root pile

One 、 Preface

This article mainly takes the small root heap as an example , Take some knowledge notes about the small root pile , The front is mainly heap sorting , The following is an introduction to a topic , Because of the particularity of that topic , So don't go into details , This article mainly takes some operations that can be realized by heap as examples , Record some applications of heap .

Two 、 understand

The main audience of this article is based on knowing the establishment of binary tree , Record the heap . If you don't know much about binary trees uu You can first learn about the establishment of binary trees , Know how the nodes of left and right children are represented , Then eat this article .

Pile , In fact, the prototype is a complete binary tree , We know , A complete binary tree must ensure the integrity of its son , That is, a node is x Father , If he has children , Then the node position of his left and right children must be 2x and (2x+ 1), The root node coordinates of the whole tree are from 1 Start calculating ！

The heap is actually divided into small root heap and large root heap . Take the small root pile as the main example . Small root , The roots are all small , That is, if a node has children , Then he is between himself and his children , He is the youngest . That is our small root pile . As for the small root pile , Take the following figure as an example , I believe you can know more clearly .

Above is a small pile of roots , The red color represents the coordinates of each node .

3、 ... and 、 Heap correlation function

I think we should first take the relevant functions of the heap as an example, and then explain the basic operations of the subsequent heap

① Define related variables

const int N = 100050;
int h[N]; // Store the elements of the heap 
int sz = 0; // Represents the size of the heap 

②down function

If some nodes have changed , It may cause the node to need to be adjusted down to the appropriate position

void down(int u) {
    // Record the node and child who is the youngest , The little one will come to his father's position , Become the root 
    int t = u;
    // If the left child exists , And smaller than root 
    if(2*u <= sz && h[t] > h[2*u]) t = 2*u;
    // If there are children , And younger than Gen and Zuo 
    if(2*u+1 <= sz && h[t] > h[2*u+1]) t = 2*u+1;
    // If recorded at this time t It's not equal to u Words 
    if(t != u) {
        swap(h[t], h[u]);
    	// Deal with the subsequent nodes recursively 
    	down(t);
    }
}

③up function

If some nodes have changed , It may cause the node to need to be adjusted upward to the appropriate position , The difference between upward adjustment and downward adjustment is , When adjusting upward , Just compare with the root node , Because in order to meet the needs of small root pile , Among them, children have changed , But in the previous state , The root is still guaranteed to be the smallest .

void up(int u) {
    // When the root node is larger than the changing child , Let him adjust upward 
    while(u / 2 > 0 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

Four 、 Basic operation of the heap

Through the introduction of heap related functions, the following is actually a patchwork of functions

① Build a heap

Here is a clever way , No matter what kind of small root pile , If it contains n Elements , Then leaf nodes ( No child node layer ) The parent node of the last existing element on the upper layer of is n / 2, This conclusion can be directly remembered . So when we build the heap , We only need the slave node to be n / 2 Start to adjust the node upward at , Each node goes down down You can build a heap once .

// This operation can put a one-dimensional array containing elements , Arrange according to the node order of the heap 
for(int i = n / 2; i > 0; i -- ) {
    down(i);
}

② Insert an element into the heap

Here's a trick: the following points

• Insert the inserted element at the end of the heap first
• utilize up Adjust the function upwards

h[++sz] = val;
// Adjust the last element of the heap up 
up(sz);

③ Delete the elements in the heap

• The element to be deleted and the last element in the heap
• up Adjust it again
• down Adjust it again

Only one of the last two steps will be carried out , Because after adjustment , Or he is younger than his father , Otherwise, he will be older than the child .

swap(h[k], h[sz]);
sz--;
up(k);
down(k);

④ Modify the value of an element in the heap

Similar to the third operation

• Modify the element value in the heap
• up Adjust it again
• down Adjust it again

h[k] = val;
up(k);
down(k);

⑤ Output the minimum value in the heap

• Just output the top elements directly

cout << h[1] << endl;

It's not hard to find out , In fact, the adjustment of the whole pile is similar to boxing king , Let's first know what skills each hero has , Then according to different needs , Use our known skills , Play different combination skills , Final KO other party . And we just want to use the combined functions AC Related algorithm questions . It's still fun ！

5、 ... and 、 Related topics

Topic 1 . Heap sort

The main reason why we can use heap sorting is that the small root heap can maintain the minimum value in our whole heap . When the minimum value is output , We delete the top element , Then constantly output new heap top elements , We can finish this topic . So we only need to use the ①③⑤ Combined skills, we can AC It fell off

complete AC Code

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int m, n;
int sz, h[N];

void down(int x) {
    int t = x;
    // The left subtree exists and is smaller than the node 
    if(2 * x <= sz && h[2 * x] < h[t]) t = 2 * x;
    // The right subtree exists and is smaller than the node 
    if(2 * x + 1 <= sz && h[2 * x + 1] < h[t]) t = 2 * x + 1;
    if(t != x) {
        swap(h[t], h[x]);
        down(t);
    }
}

int main() {
    cin >> n >> m;
    sz = n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = n / 2; i; i--) down(i);
    while(m--) {
        cout << h[1] << " ";
        h[1] = h[sz--];
        down(1);
    }
    return 0;
}

Topic two

This topic is to record the first k The position of the number of insertions , So you can directly use the structure to install the number of inserted nodes in each node , But for speed , It can be implemented in a similar way to using arrays to simulate hash tables , Because it may be a little difficult to understand . I wrote relevant comments in the code , You can understand it according to your ability .

//ph[k] It means the first one k Subscript of inserted nodes in the heap ,hp[k] Indicates the... In the heap k The number of nodes is the number of inserts .

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int ph[N], hp[N], h[N];
//m On behalf of the m The number of inserts ,cnt Represents the size of the entire heap 
int m, cnt;
// This swap It realizes not only element exchange , The number of inserted nodes is also exchanged ！
void heap_swap(int a, int b) {
    // Swap the subscript in the heap of a certain inserted number 
    swap(ph[hp[a]], ph[hp[b]]);
    // A node in the swap heap represents the number of inserts 
    swap(hp[a], hp[b]);
    // Swap the values of two positions in the heap 
    swap(h[a], h[b]);
}

// Download operation 
void down(int x) {
    int t = x;
    if(2 * x <= cnt && h[2 * x] < h[t]) t = 2 * x;
    if(2 * x + 1 <= cnt && h[2 * x + 1] < h[t]) t = 2 * x + 1;
    if(t != x) {
        heap_swap(t, x);
        down(t);
    }
}

// Upload operation 
void up(int x) {
    while(x / 2 && h[x / 2] > h[x]) {
        heap_swap(x, x / 2);
        x >>= 1;
    }
}

int main() {
    int num, k, n;
    cin >> n;
    string op;
    while(n--) {
        cin >> op;
        // The insert 
        if(op == "I") {
            cin >> num;
            cnt++; m++;
            h[cnt] = num; hp[cnt] = m; ph[m] = cnt;
            up(cnt);
        }
        // Output min 
        else if(op == "PM") {
            // cout << n << endl;
            cout << h[1] << endl;
        }
        // Delete minimum 
        else if(op == "DM") {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        }
        // Delete the first k The number of inserts 
        else if(op == "D") {
            cin >> k;
            // You must save a location first , Otherwise, the pointer position may be directly exchanged in the exchange process , Cause the answer to be wrong ！！
            k = ph[k];
            heap_swap(k, cnt);
            cnt--;
            up(k);
            down(k);
        }
        // Amendment No k The number of inserts is num
        else {
            cin >> k >> num;
            int id = ph[k];
            h[id] = num;
            up(id);
            down(id);
        }
    }
    return 0;
}

 author ：sheepice
 link ：https://www.acwing.com/activity/content/code/content/3438577/
 source ：AcWing
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .