Summary of tree and heap knowledge points

One 、 Trees

1. The definition of a tree

Trees （ English ：Tree） Is an undirected graph （undirected graph）, There is a unique path between any two vertices . Or say , As long as there is no loop, the connected graph is a tree .

Binary tree （ English ：Binary tree） There are at most two branches per node ( There is no branching degree greater than 2 The node of ) The tree structure of the . Usually branches are called “ The left subtree ” and “ Right subtree ”. The branches of a binary tree have left and right order , Can not be reversed. .

Perfect binary tree ： Leaf nodes can only appear in The lowest and lower layers , And the nodes of the lowest layer are concentrated in this layer Leftmost A binary tree with several positions of .

Balanced binary trees ： It's a tree Empty tree Or its left and right subtrees The absolute value of the height difference does not exceed 1, And both the left and right subtrees are a balanced binary tree .

2. The application of tree ：

Fast data retrieval ：

• STL Red and black trees
• Database B+ Trees

Document structure organization ：DOM

Artificial intelligence ： Decision tree

game ： Realize fast collision detection by constructing spatial tree （ https://www.zhihu.com/question/25111128 ）

Merkel tree of blockchain

3. Commonly used algorithm

recursive ： Depth first traversal of trees （https://blog.csdn.net/weixin_41876155/article/details/80905220）

Binary search tree ： Left node value < Root node value < Right node value

queue ： Breadth first traversal of trees （ Hierarchical traversal ）（https://blog.csdn.net/weixin_41876155/article/details/80905220）

Two 、 Pile up

1. The definition of the heap  

Heap is realized by constructing binary heap （binary heap）, A kind of binary tree ; Because of the universality of its application , When unlimited , All refer to the realization of the data structure . This data structure has the following properties ：

• Any node less than （ Or greater than ） All its descendants , Minimum element （ Or maximum element ） On the root of the pile （ Heap sequence sex ）.---> The smallest pile / The biggest pile
• The pile is always one Complete tree . That is, except for the bottom layer , Nodes in other layers are filled with elements , And the lowest layer should be filled in from left to right as much as possible .
• The root node i, The left node 2 * i + 1, Right node 2 * i + 2.

2. The process of building the pile ：

Code implementation ： （Lintcode 130: Heapify）

Description

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity.

answer （ Overtime ）--- The magic is , Pull out the function without timeout , Let me study it slowly later ……

Ideas ： Find the leaf node and compare it with its root node

public class Solution {
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
    public void heapify(int[] A) {
        // write your code here
        for(int i = (A.length - 1)/2; i >= 0; --i){
            while(i < A.length){
                int left = 2 * i + 1;
                int right = 2 * i + 2;
                int min_pos = i;
                if(left < A.length && A[left] < A[min_pos]){
                    min_pos = left;
                }
                if(right < A.length && A[right] < A[min_pos]){
                    min_pos = right;
                }
                if(min_pos != i){
                    int temp = A[i];
                    A[i] = A[min_pos];
                    A[min_pos] = temp;
                    i = min_pos;
                }
                else{
                    break;
                }
            }
        }
    }
}

Complexity analysis of reactor building ：

• N The maximum heap height of nodes is h=logN, The lowest non leaf node can be adjusted at most 1 Time , Last but not least 2 The most layers 2 Time ,… And so on , The root node needs at most h Time .
• The lowest level of child nodes share 2^(h-1) individual , Last but not least 2 Layer has a 2^(h-2) individual ,… And so on , The root node has 2^(h-h) individual 1 individual .
• So the total time complexity is 1^(h-1) + 2*2^(h-2) + (h-1)*2 + h, The result is N*2 – 2 – log(N), So time complexity O(n).

3. Merge K Sorted List

Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length == 0)
            return null;
 
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){  // Realize heap with priority queue 
            public int compare(ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
 
        ListNode head = new ListNode(0);
        ListNode p = head;
 
        for(ListNode list: lists){
            if(list != null)
                queue.offer(list);  // Maintain a minimum heap , Into the heap list Elements , As the sample ,1,1,2
        }    
 
        while(!queue.isEmpty()){
            ListNode n = queue.poll();
            p.next = n;
            p = p.next;
 
            if(n.next != null)   // Into the heap 4
                queue.offer(n.next);
        }     
        return head.next;
    }
}

3. Application of heap

Priority task scheduling

• How can the operating system schedule quickly according to thread priority ？

Multiple merging and sorting of massive data

• Favorite interview questions , Massive data sorting selection topK.