heap

Priority queue

A special "queue" in which elements are taken out according to the priority (keyword) size of elements rather than the order in which elements enter the queue.
Implementation method:
(1) Arrays: inserting (elements are always inserted at the end)
Delete (find the largest or smallest keyword and delete the element to be moved from the array)
(2) Linked list: insert (elements are always inserted into the head of the linked list)
Delete (find the largest or smallest keyword and delete the node)
(3) Ordered array: insert (find the appropriate position, move the elements and insert)
Delete (delete last element)
(4) Ordered linked list: insert (find the appropriate position and insert elements)
Delete (delete the first or last element)

The essence of heap

Structure: the essence of heap is a complete binary tree represented by array.
Ordering: the keyword of any node is the maximum (minimum) value of all nodes of its subtree
It is expressed as the order of the node sequence on the path from the root node to any node!
Maximum heap (large top heap) minimum heap (small top heap)

Maximum heap operation

typedef struct HeapStruct *MapHeap;
struct HeapStruct{
   int*a;//An array that stores heap elements
   int size;//Number of current elements in the heap
   int capacity;//Maximum capacity of the heap
   };

MaxHeap create(int MaxSize)
{
MaxHeap H=malloc(sizeof(struct HeapStruct));
H->a=malloc((maxsize+1)*sizeof(int));
H->size=0;
H->capacity=MaxSize;

H=>a[0]=MaxData;//H - "a[0] is the sentinel element, which is not less than the largest element in the heap. Define "sentinel" to be greater than the possible values of all elements in the heap for faster operation
}

Algorithm: insert the new node into the ordered sequence from its parent node to the root node

void Insert(MaxHeap H,int item)
//Insert the element item into the maximum heap h, and define H - > a [0] as a sentinel
{
  int i;
  if(IsFull(H)){
    printf("Maximum heap full");
    return;
    }
    
  i=++H->size;//i points to the position of the last element in the heap after insertion
  for(;H->a[i/2]<item&&i>1;i/=2)
   {
       H->a[i]=H->a[i/2];//Downward filtering node
    }//i represents the current position to be placed in, and i/2 is the parent node
   H->a[i]=item;//Insert item into
}

Deletion of maximum heap

Take out the element of the root node (maximum value) and delete one node of the heap at the same time.
T(N)=logN

int delete(MaxHeap H)
{//Extract the element with the largest key value from the maximum heap H, and delete a node
  int parent,child;
  int maxitem,t;
  if(isempty(H)){
    printf("Maximum heap empty);
    return;
    }
    maxitem=H->a[1];//Get the maximum value of the root node, that is, the element to be deleted
    //Use the last element in the large root heap to filter the lower nodes from the root node upward
    t=H->a[H->size--];
    for(parent=1;parent*2<=H->size;parent=child)
    {//Determine whether there is a left son
        child=parent*2;//Let's assume that the left son is older
        //Child points to the largest of the left and right child nodes
        if(child!=H->size&&H->a[child]<H->a[child+1])
           child++;
        if(t>=H->a[child]) break;
        else//Move t to next level
           H->a[parent]=H->a[child];
      }//Find a place for t
    H->a[parent]=t;
    return MaxItem;
 } 

Establishment of maximum heap

Create maximum heap: store the existing N elements in a one-dimensional array according to the requirements of the maximum heap.
Method (1): insert N elements into an initially empty heap one by one through the insertion operation. The time cost is O (NlogN)
Method (2): establish the maximum heap O(n) in linear time complexity
(1) The N elements are stored in the input order to meet the structural characteristics of the complete binary tree.
(2) Adjust the position of each node to meet the order characteristics of the maximum heap

Hashtable

Hash table unorderderdedset unorderdedmap

Hash table Basics

1. Hash table can be understood as a collection structure in the use layer.
2. If there is only key but no value, use unorderderdedset; If both key and value exist, it is unorderderdedmap
3. Using the addition, deletion and deletion of hash table, it can be considered that the time complexity is O (1), but the constant time is very large.
4. If the thing put into the hash table is the basic type, the internal stack value is passed, and the memory occupation is the size of this thing.
5. If the thing put into the hash table is a user-defined type, it will not copy one, and the address will be passed. The size of memory occupied is the size of the memory address of this thing.

chart

Basic concept of graph

The chart shows a many to many relationship. Contains a set of vertices (usually v for the set of vertices and E for the set of edges)

Storage structure of graph

Storage form of graph: adjacency table + adjacency matrix
Graph composition: Point Set + edge set
(1) Adjacency table method: take the point set as the unit, and write out the direct neighbors of each point.
G[N [is a pointer array, corresponding to a linked list in each row of the matrix, and only non-0 elements are stored.
In the network, the weighted domain should also be added.
Adjacency table: it is convenient to find all "adjacency points" of any node, save the space of sparse graph (N head pointers + 2N nodes are required), and it is convenient to calculate the degree of any vertex for undirected graph. For a directed graph, only degrees can be calculated. You need to construct an "inverse adjacency table" (store the edges pointing to yourself) to calculate the "penetration".

(2) Adjacency matrix method: if there is no connection, the distance is infinite.
Two dimensional array stores G[N][N] - N vertices from 0 to N-1 edges
Use A one-dimensional array A with length N (N+1)/2 to store G00, G10, G11... Gn-1, N-1
For the network, just define the value of G[i][j] as the weight of edge < VI, VJ >.
Benefits:
(1) Simple, intuitive and easy to understand
(2) It is convenient to check whether any pair of vertices have edges
(3) all adjacent points that are convenient for finding people
(4) It is convenient to find the degree of any vertex (the number of edges from this point is called out degree, and the number of edges pointing to this point is called in degree)
Undirected graph: the number of non-0 elements in the corresponding row (column)
Directed graph: the number of non-0 elements in the corresponding row is "out degree"; The number of elements whose corresponding column is not 0 is called "in degree"
Disadvantages: it wastes space (a lot of space is wasted in storing sparse graphs), but it is more cost-effective for dense graphs

Breadth first search (BFS)

void BFS(Vertex V)
{
    visited[V]=true;
    Enqueue(V,Q);
    while(!isempty(Q))
    {
      V=dequeue(Q);
      for(V Each adjacency point of w)
        if(!visited[w]){
           visited[w]=true;
           Enqueue(w,Q);
           }
     }
 }

N vertices, E edges, time complexity:
Adjacency table: O (N+E)
Adjacency matrix: O (N^2)
Method: implement all algorithms according to your favorite way.
3. Edges are vertex pairs (V, E) ∈ v-W
The directed edge < v, w > represents the value from v to W
Double edges and self loops are not considered.

Depth first search:

void DFS(Vertex V)
{
  visited[v]=true;
  for(v Each adjacency point of w)
    if(!visited[w])
       DFS(w);
}

If there are N vertices and E edges, the time complexity is
(1) Store graph with adjacency table, O(N+E)
(2) Storing graphs with adjacency matrix, O(N^2)

What if the graph is not connected

Connected (if there is an undirected path from v to w, it is said to be connected)
Path: the path from v to w is a set of vertices, in which any pair of adjacent vertices have edges in the graph. The length of the path is the number of edges in the path (if weighted, it is the sum of the weights of all edges). If all nodes from v to w are different, it is called a simple path.
Circuits: paths with start equal to end
Connected graph: any two vertices in the graph are connected
Connected components: polar connected subgraphs of undirected graphs
Maximum vertex number: one more vertex will be disconnected
Maximum number of edges: contains all edges connected by all vertices in the subgraph
Strongly connected: if there is a bidirectional path between vertices v and w in a directed graph, then v and w are strongly connected
Strongly connected graph: any two vertices in a directed graph are strongly connected
Strongly connected components: maximal strongly connected subgraphs of directed graphs

void DFS(Vertex V)
{
  visited[v]=true;
  for(V Each adjacency point of w)
    if(!visited[w])
      DFS(w);//Every time DFS is called, the connected component of v is traversed once
 }

Harman tree and Harman coding

According to different search frequencies of nodes, a more effective search tree is constructed.
Weighted path length (WPL): let the binary tree consist of N sub leaf nodes, each leaf node has a weight Wk, and the length from the root node to each leaf node is lk, then the sum of the weighted path lengths of each leaf node is the sum i from 1 to n WiLi
Optimal binary tree (Harman tree): the smallest binary tree in WPL.

Construction of Harman tree

Merge the two binary trees with the smallest weight each time.

typedef struct TreeNode*HuffmanTree;
struct TreeNode{
  int weight;
  HuffmanTree left,right;
 }

HuffmanTree Huffman(MinHeap H)
{//Suppose that H - > size weights already exist in H - > a [] - > weight
  int i;
  HuffmanTree T;
  BUildMinHeap(H);//Adjust H - > a [] to the minimum heap according to the weight
  for(i=1;i<H->size;i++)
  {//Do h - > size-1 consolidation
  T=malloc(sizeof(struct TreeNode));//Create a new node
  T—>Left=delete(H);//Delete a node from the smallest heap as the left child of T
  T->Right=delete(H);
  T->Weight=T->left->weight+T->right->weight;//Calculate weight
  insert(H,T);
  }
  T=deletemin(H);
  return T;
  }
  

Hallman tree features:

(1) There is no node with degree 1
(2) The Harman tree with n leaf nodes has 2*n-1 nodes
(3) After exchanging the left and right subtrees of any non leaf node of a Harman tree, it is still a Harman tree
(4) For two Harman trees composed of the same set of weights, the WPL is the same.

Harman code

Given a string, how to encode characters to minimize the encoding storage space of the string
Unequal length code: make the code with more occurrences smaller and the code with less occurrences larger.
Avoid ambiguity: add prefix code (the encoding of any character is not the prefix of another character encoding)
resolvent:
Binary tree is used for coding
(1) Left and right branches: 0, 1
(2) Characters appear only on leaf nodes

aggregate

Set operation: intersection, union, complement and difference determine whether an element belongs to a set.
Merge query set: merge sets to query what set an element belongs to.
How to realize the collection storage in the parallel query problem:

A set can be represented by a tree structure, and each node of the tree represents a set element

Set operation (1) find the set where an element is located (represented by the root node)

int find(settype s[],int x)
{
   //Find the collection of elements with value x in array s
   //maxsize is the maximum length of s
   for(int i=0;i<maxsize&&s[i].Data!=x;i++)
    {
         if(i>=Maxsize) return -1;//x not found - 1 returned
         for(;s[i].parent>=0;i=s[i].parent);
         return i;//Find the set to which x belongs and return the subscript of the tree node in the array s
     }
 }

Union of sets
(1) Find the root node of the set tree where x1 and x2 elements are located respectively
(2) If they are different roots, the parent node pointer of one root node is set to the subscript of the array of the other root node
(3) In order to improve the search performance after merging, small sets can be merged into large sets.

void Unior(SetType s[],int x1,int x2)
{
  int r1,r2;
  r1=find(s,x1);
  r2=find(s,x2);
  if(r1!=r2) s[r2].parent=r1;
 }