This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Definitions and properties of a heap:
Heap: a data structure that represents a full binary tree as a one-dimensional array. The so-called binary tree is a kind of tree, each parent node, there are at most two child nodes, generally called left and right subtrees
Perfect binary tree: a binary tree whose number of layers is K and whose number of elements is 2k-1
And a complete binary tree can be understood as a perfect binary tree without part or without part, but the content must be filled from top to bottom, from left to right, that is, the missing part is always on the right;
Small root heap: that is, the root node is less than or equal to its left child, and also less than or equal to its right child, and each point is less than the left and right child nodes; The left child is the minimum of the left set, and the right child is the minimum of the right
The root node is the minimum value of left and right children –> Deduce: the root node is the minimum value of the heap
How to hand write a heap:
The premise of handwriting heap is to master the basic method of adding, deleting, modifying and checking. The operation of Dwon and UP is implemented in the following code. The basic method is as follows
Size –> indicates the size of the heap;
-
Insert a number:
heap[++size] = x; up(size); Copy the code -
Find the minimum value in the set
heap[1]; Copy the code -
Delete minimum value:
heap[1] = heap[size]; size--; down(1); Copy the code -
Delete any element:
heap[k] = heap[size]; size--; down(k); up(k); Copy the code -
Modify any element:
heap[k] = x; down(k); up(k); Copy the code
Heap sort:
Step :(output the minimum value of the first m)
- Initialize the heap
- Building the heap
- Down the operation
The realization process of down operation:
Compare the minimum value of the three points, if it does not meet the definition of the heap then swap and recursively perform down
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
/ / define the heap
static int[] h = new int[N];
// Determine the size of the heap
static int size;
// When the number is larger than the three numbers, make the number sink
public static void down(int u){
// Set the minimum value of the three numbers to t;
int t = u;
// u*2 is the left son of u; U *2+1 is the right son of U;
// If the subscript of the left son is less than the size of the heap, then this point exists;
// If the value of left son is smaller than the value of the minimum t, then t refers to left son
if(u*2 <= size && h[u*2] < h[t]) t = u * 2;
// If the subscript of the right son is less than the size of the heap, then this point exists;
// If the value of the right son is smaller than the value of the minimum t, then t is pointed to the right son
if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
// If the minimum value of the last t is not itself (u);
// Then swap the values of the two subscripts; Switch over in down, to prevent damage to the heap structure;
if(t ! = u){inttemp = h[u]; h[u] = h[t]; h[t] = temp; down(t); }}public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split("");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
String[] str = br.readLine().split("");
// Initialize the heap
for(int i = 1; i <= n; i++){
h[i] = Integer.parseInt(str[i-1]);
}
// Set the heap size
size = n;
// Get the time complexity by recursion: build the heap --> time complexity is O(n)
for(int i = n/2; i ! =0; i--){ down(i); }while(m-- ! =0) {// Output the current minimum value, which is the top of the heap
bw.write(h[1] +"");
// Remove the last value from the top of the heap
h[1] =h[size];
// Heap size --
size--;
// Put the top of the heap down to find the minimum value;
down(1); } bw.flush(); br.close(); bw.close(); }}Copy the codeImplement up operation:
U /2 is the parent node of U, h[u] < h[u/2]–> the child node is smaller than the parent node; After the switch, up(u parent node);
First the heap is a full binary tree :(here are the numbers)
One, two, three, four, five, six, sevenCopy the code2/2 = 1, 3/2 = 1.
4/2 = 2, 5/2 = 2, 6/2 = 3, 7/2 = 3
Through the above operation can find the parent node;
public static void up(int u){
if(u / 2 > 0 && h[u] < h[u / 2]){
heapSwap(u, u / 2);
up(u/2); }}Copy the codeSimulate:
The core of the simulation heap implementation is to write down operations, up operations, and swap operations.
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int[] ph = new int[N]; // Store the index of the KTH point
static int[] hp = new int[N]; // Store the value of the point in the queue in which the value is inserted
static int size; // The size of the heap is the current number of data
public static void down(int u){
int t = u;
if(u*2 <=size && h[u*2] < h[t]) t = u*2;
if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
if(t != u){
heap_swap(u,t);
down(t);
}
}
public static void up(int u){
if(u / 2 > 0 && h[u] < h[u / 2]){
heap_swap(u,u/2);
up(u/2); }}public static void heap_swap(int u,int v)
{
/ /
// swap(h[u],h[v]); / / value exchange
// swap(hp[u],hp[v]); // Swap the insertion order (number) of the points in the heap
// swap(ph[hp[u]],ph[hp[v]]); // Exchange the values of number h[u] h[v]
swap(h,u,v);
swap(hp, u, v);
swap(ph, hp[u], hp[v]);
}
public static void swap(int[] a, int u, int v){
int tmp = a[u];
a[u] = a[v];
a[v] = tmp;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
size = 0;
int m = 0;
while(n-- ! =0){
String[] s = br.readLine().split("");
String op = s[0];
if("I".equals(op)){
int x = Integer.valueOf(s[1]);
m++;
h[++size]=x;
// ph[m]=size;
// hp[size]=m;
// Create a mapping relationship where the MTH insert number is size; // Create a mapping relationship where the MTH insert number is size;
ph[m] = size;
// Insert the MTH number under the size number;
hp[size] = m;
// Adjust the number of inserts upwards
up(size);
}else if("PM".equals(op)) bw.write(h[1] +"\n");
else if("DM".equals(op)){
heap_swap(1,size);
size--;
down(1);
}else if("D".equals(op)){
int k = Integer.parseInt(s[1]);
int u=ph[k]; // Make sure u= pH [k] is used to store the index of the KTH insertion point
heap_swap(u,size); // Because the value of ph[k] has already occurred after heapSwap
size--; // If ph[k] is still used in up,down operations, an error will occur
up(u);
down(u);
}else if("C".equals(op)){
int k = Integer.parseInt(s[1]);
int x = Integer.parseInt(s[2]);
h[ph[k]]=x; // There is no heapSwap operation involved and only one of the following up and down operations will occur
down(ph[k]); // So you can directly pass in pH [k] as the parameterup(ph[k]); } } bw.flush(); br.close(); bw.close(); }}Copy the codeTo make it easier to read, I wrote comments in the code, not out of it, so that the reader can understand.
The end:
If you see here or just to help you, I hope you can point to follow or recommend, thank you;
If there are any errors, please point them out in the comments and the author sees them will be corrected.