A Reading Note

Book review :《ACM/ICPC Algorithm training course 》 This book is Yu Ligong Chief editor's , Code from Nanjing university of science and technology ACM intense training team The code base , So after reading it, Xiao Bian found that it was very practical , It's suitable for training ~~, I listened to the training team at that time final I bought it with my opinion , It still feels good .

Relative to others ACM For books , Of course, as the title says , This is an algorithm training book , There are a lot of algorithms, practical topics and code , Although Xiaobian still found some mistakes = =, The word order habit of some notes is also a bit out of my taste . There are many practical problems, such as water , But that's why it helps a lot of beginners , I think it's a good algorithm book , Of course, self-study still needs a lot of effort .

Xiaobian thinks that this book is mainly aimed at beginners who want to have a comprehensive understanding of the content of the algorithm competition , Students who want to study algorithms alone can chew 《 Introduction to algorithms 》,ACM Come on, you great gods, wipe out Liu Rujia's big black book

The children who have just started will join me fighting ah = =


Don't talk much , Let's get to the point , ( Some of the concepts in this section come from this book P25-2.1.3 Pile up , The rest are original )

The concept of heaps :

Heap in data structure (heap) It means a Perfect binary tree , Of course, it can be realized with linked list , You can also use one-dimensional arrays ( linear ) To simulate the implementation .

According to the size of the data stored in the heap , Heaps fall into two categories , One is The biggest pile , One is The smallest pile .

  • The biggest pile : The value of any node is greater than or equal to the value of any child node , So the root of the largest pile (root) It must be maximun.
  • The smallest pile : The value of any node is less than or equal to the value of any child node , So the root of the smallest heap (root) It must be minimun.

The realization of the heap

We often hear that ,heap It's an efficient and compact data structure , So why efficient and compact . Let's make a brief introduction with a picture .( The following figure Up and down are heap Array ( use heap[] Express ),heap Icon )

ps: The complete binary tree in the figure above can be used as heap Icon , The green column above is the corresponding array (array), for example 16 Namely heap[1],14 Namely heap[2]... By analogy .

We are used to 14 and 10 be called 16 The child node of ,14 by 16 The left son ,10 by 16 Right son of .

So like this , We can start with arrays (array) Get in heap[2],heap[3] by heap[1] The child node of ,heap[4],heap[5] by heap[2] The child node of ....

adopt c/c++ Plastic division rules , obtain 2/2 = 1 , 3/2 = 1; So we put Where the data is Satisfy s/2 =f  Formula s Referred to as f The child node of (son), f Referred to as s The parent node (father), In this way, we can use arrays to store this series of data compactly and neatly , Next time you call a location p The parent node of , Direct adoption p/2 You can find it p The parent node of , Empathy , The child node is p*2 and p*2+1, Is the data stored in this way neat and easy to find .( Although Xiaobian thinks that the function of handwriting this data structure will still be a little cumbersome = =)


Heap operation :

Now let's see how the general operation of this data structure can be realized by code ?( Multi code alert ~~)( For beginners, it's easy to understand after more debugging ~~fighting!)

  • Delete the element with the highest priority -DeleteMin()  ——   Delete... For example - The smallest pile of heap[1]

This operation is divided into three steps :

  1. Delete the root directly (root);
  2. Replace... With the last element root;
  3. take heap Readjust down ;———— The third step is represented by the next called Adjust the heap function - down(
     /* Delete the element with the highest priority */
    /* Take the minimum heap as an example */ /* heap - down_adjustment */
    void down(int p) //current_node
    {
    int q = p*; //left_son_node
    int a = heap[p]; while (q < hlength) //hlength refer to heap The length of the array , That's the total number of elements in the heap
    {
    if(heap[q] > heap[q+]) //find_min_son
    q++; if(heap[q] < a) //complete_adjustment
    break;
    else
    {
    heap[p] = heap[q];
    p = q;
    q = p*;
    }
    }
    heap[p] = a;
    return;
    } /* delete_minimun_node */
    int DleteMin()
    {
    int r = heap[]; //delete_root
    heap[] = heap[hlength--];
    down(); //this is the key point!!
    return r;
 /* Delete the element with the highest priority */
/* Take the minimum heap as an example */ /* heap - down_adjustment */
void down(int p) //current_node
{
int q = p*; //left_son_node
int a = heap[p]; while (q <= hlength) //hlength refer to heap The length of the array , That's the total number of elements in the heap
{
if(q < hlength && heap[q] > heap[q+]) //find_min_son
q++; if(heap[q] < a) //complete_adjustment
break;
else
{
heap[p] = heap[q];
p = q;
q = p*;
}
}
heap[p] = a;
return;
} /* delete_minimun_node */
int DleteMin()
{
int r = heap[]; //delete_root
heap[] = heap[hlength--];
down(); //this is the key point!!
return r;
}

View Heap-Code

  • Insert new elements into the heap -Insert(x)—— Still take the smallest heap as an example ( Do not understand still remember to understand step by step , You'd better debug it yourself )

The operation steps are: :

  1. It's going to be insert The elements of x Add to the end ;
  2. Adjust up ;———— The second step is to use the called up() Function representation ;
 /* Insert new elements into the heap */
/* Take the minimum heap as an example */ /* heap - up_adjustment */
void up(int p) //current_node
{
int q = p/; //partner_node
int a = heap[p]; while(q > && a < heap[q])
{
heap[p] = heap[q];
p = q;
q = p/;
}
heap[p] = a;
return;
} /* Insert_new_node */
void Insert(int a)
{
heap[++hlength] = a; // Lengthen and make a Add to the end
up(hlength);
}

View Heap-Code

  •   take x The priority of location is raised to p value :IncreaseKey(x,p);
 /* In the pile x Priority raised to p */
void IncreaseKey(int x,int p)
{
if (heap[x] < p) // if heap[x] Itself is less than p, that x It's better than p high
return;
heap[x] = p; // Otherwise it would be heap[x] The assignment is p
up(x); // Call the function above up()
}

View Heap-Code

  • Array simulation build heap :Build()——(⊙o⊙) forehead , Forgive me for building the last pile , In fact, this is also the normal order = =
 /* Array build heap */
void Build()
{
for (int i = hlength / ; i > ; i++)
down(i); // Call the first Adjust the heap function
}

View Build_heap-Code


Time analysis of the reactor :
  • Up and down, each layer is a constant level , common log n layer , therefore Adjust the heap The degree of time O(log n);
  • Insert / Delete   Call up or down adjustment only once , So it's all O(log n);
Now you can see why the time efficiency of heap is so high ~~
 

Example of the smallest heap : ———— Real combat is the only test of truth = =, In fact, it is also the only standard for learning code
Source:POJ 2051 ———— if cin and scanf It is better to use the latter in algorithm competition , Because maybe the former will contribute more than ten to you TLE= =
 
It means :
Enter the data and give you a number for each line , And give you the interval between each time it appears , Finally “#” end
  There's another one at the end of the file k, And then let you show them up from morning till night k Print out a number , If there are multiple numbers at the same time , Then output the small number first .
Feasibility analysis of minimum reactor structure :
 1. First read in the data , Read it in and insert it into the heap , After reading in the data, an initial heap is built .
2. Then output the top element , Add the value of the top element to the time interval it appears , And then it goes down , Until it finds a place in the heap .
3. Repeat step 2 Until before k Number output completed .
 
 //Argus- Chinese seems to be a mythical character Argos It's called a giant with a hundred eyes ~~
// Roar, roar = =( This plot has nothing to do with the title ) // The loop maintains the minimum heap
//Time:32Ms Memory:176K
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 1001 struct Argument {
int name; // Number
int now; // Current execution time
int period; // cycle
friend bool operator < (Argument &a, Argument &b) {
return a.now < b.now || (a.now == b.now && a.name < b.name);
}
}arg[MAX]; int len = ; /* from x Downward adjustments */
void down(int x)
{
Argument tmp = arg[x];
int next = * x;
for (int next = * x; next < len;next *= )
{
// Compare the priority of child nodes
if (next + < len && arg[next + ] < arg[next])
next++;
// It can't be lowered
if (tmp < arg[next]) break;
// Down regulation
arg[x] = arg[next];
x = next;
}
arg[x] = tmp;
} void createHeap()
{
for (int i = len / ; i > ; i--)
down(i);
} int main()
{ char command[];
while (scanf("%s", command), strcmp(command, "#"))
{
scanf("%d%d", &arg[len].name, &arg[len].period);
arg[len++].now = arg[len].period;
} createHeap(); int k;
scanf("%d", &k);
for (int i = ; i < k; i++)
{
printf("%d\n", arg[].name);
arg[].now += arg[].period;
down();
} return ;
}
 

 
Um. , That's it = =, I hope to record   A kind of My university , I also hope that I can give you some advice ACM New people  or  Algorithm beginners some suggestions and some related collation
I hope I didn't miss my children ,hhhhhhhhhhh
——————————From  Xiaomo

Algorithm notes And data structure ( Pile up )(POJ 2051) More articles about

  1. Algorithm notes And data structure ( Line tree details )(POJ 3468)

    Continue the first reading notes , This one is based on <ACM/ICPC Algorithm training course > The summary and modification of the explanation of line segment tree on ( This book is here in the line tree Error A lot ), But in general, the explanation and cases of specific algorithms in this book are not ...

  2. Algorithm notes And data structure ( And check the collection for details )(POJ1703)

    <ACM/ICPC Algorithm training course > Reading notes - This time, add and look up the part of the collection . We will elaborate on the idea of union search , And attach me AC fall POJ1703 Of Code. In some cases N In the application of set of elements , Usually each yuan will be ...

  3. Basic data structure —— Pile up (Heap) The basic concept and operation of

    Basic data structure ―― The basic concept of heap and its operation Little ad : Fujian Anxi No.1 Middle School online evaluation system Online Judge When I first heard the word heap , I think it's a collection of things ... But actually, it uses the structure of complete binary tree to maintain a group of ...

  4. C Data structure heap

    introduction - Data structure heap I'm familiar with the structure of the pile , From heap sort to priority queue , We always see it . There's too much information , Pile up - https://zh.wikipedia.org/wiki/%E5%A0%86%E7 ...

  5. java data structure ---- Pile up

    1. Pile up : Pile is a kind of tree , The time complexity of priority queue insertion and deletion implemented by it is O(logn), Although the priority queue implemented by heap is slower than that implemented by array , But it takes much faster to insert . When speed is important and there are many insertions , You can choose the heap ...

  6. Algorithm design and data structure learning _5(BST&amp;AVL&amp; A brief introduction to the red black tree )

    Preface : The main purpose of this section is to give BST,AVL And the red black tree C++ Code , Convenient for your future reference , The code is still data structures and algorithm analysis in c++ (second ed ...

  7. data structure - Pile up Java Realization

    data structure - Pile up Java Realization . Achieve automatic heap growth /** * data structure - Pile up . Automatic growth * */ public class Heap<T extends Comparable> { priva ...

  8. data structure - Pile up (Heap)

    data structure - Pile up (Heap) 1. The definition of the heap The form of heap satisfies the definition of complete binary tree : if i < ceil(n/2) , The node i For branch nodes , Otherwise, it is a leaf node Leaf nodes can only appear in the largest two layers , And the leaves on the largest level ...

  9. [ACM Training ] Algorithm Elementary And data structure And Stack stack+ queue queue ( Basics + Advanced +POJ 1338+2442+1442)

    Once again, we are faced with the learning of basic data structures such as stack and queue , It should be done in many ways , Multi dimensional learning . First , These two data structures are commonly used , There are corresponding structures in the standard library that can be used directly , So the first stage should be to learn to use it directly , next ...

Random recommendation

  1. Perfect solution , The browser drop-down shows the URL problem | Perfect solution , Use native scroll Write drop-down refresh

    stay web In the development process, we often encounter , I don't want users to drop down to see my address , Sometimes, too div There's no inertia rolling in , There's something wrong with it iScroll This frame of scrollbars , But it's not worth using a framework just for an experience , today ...

  2. rds Material collection

    rds: Cloud database for short (Relational Database Service) RDS There are two types of databases currently supported :mysql,sqlserver. Alibaba cloud RDS Database tutorial rookie how to play with alicloud RDS?:h ...

  3. C# hook HOOK project (1)

    Catalog   Basic concepts Operating mechanism Hook type author Basic concepts   hook (Hook), yes Windows A platform of message processing mechanism , An application can set subroutines on it to monitor certain messages in a specified window , And the monitored windows can be other processes ...

  4. Use ConcurrentDictionary Achieve lightweight caching

    A lightweight cache is needed in the project , Store reused data . Need to consider in the design :1. Make general components , Prepare for the operation results of other module methods in the future .2. The cache module needs to be interfaced , Prepare for future replacement with external caching .3. Use the default cache expiration time , single ...

  5. erlang Debugging technology etop

    etop yes erlang Process information viewing tool , Be similar to UNIX Of top. One . Configuration parameters node The measured node. Value: atom() Mandatory setcookie Co ...

  6. Angular CLI install

    install Angular A tutorial on the official website , Because of the domestic network environment , Can't access the server , Cause installation to fail . 1. Install first NodeJs Installation tutorial :http://blog.csdn.net/zengmingen/article/ ...

  7. reverse ---01.Nop、 Chinese string search 、 Save the modified program

    Basic knowledge of :(Nop: Delete jump ) gcc Compile link command : gcc -o Generate file name The source file name  gcc Compile into assembly code :gcc -o Generate file name -S The source file name VS Look at assembly code :( In debug mode ,Ctrl+F ...

  8. C#-- Integers and byte arrays byte[] Conversion between

    using System; int  i = 123;byte [] intBuff = BitConverter.GetBytes(i);     //  take  int  Convert to byte array lob.Write ...

  9. andorid Configurator components and prompt messages

    .xml <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:android ...

  10. Take off your hands ASProtect v1.2( nothing Stolen Code)

    1. load PEID ASProtect v1.2 2. load OD > 01C04200 push Run the track .0042C001 ; // entrance C3 retn AA stos byte ptr es: ...