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 ：

- Delete the root directly (root);
- Replace... With the last element root;
- 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: ：

- It's going to be insert The elements of x Add to the end ;
- 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);

**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 :**

**Feasibility analysis of minimum reactor structure ：**

//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 ;

}

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

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- Algorithm design and data structure learning _5(BST&AVL& 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 ...

- 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 ...

- 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 ...

- [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

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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/ ...

- 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 ...

- 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 ...

- andorid Configurator components and prompt messages
.xml <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:android ...

- 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: ...