【数据结构】二叉堆、TOP K 问题

不念不忘少年蓝@ 2022-11-06 14:00 136阅读 0赞

### 二叉堆、TOP K 问题 ###

*  堆（Heap）
 *   *  堆的出现，思考？
     *  堆简介
 *  二叉堆（Binary Heap）
 *   *  获取最大值
     *  最大堆 — 添加
     *  最大堆 — 添加优化
     *  最大堆 — 删除
     *  replace
     *  最大堆 – 批量建堆（Heapify）
     *   *  自上而下的上滤
         *  自下而上的下滤
     *  效率对比
 *  二叉堆代码
 *   *  堆的基本接口-Heap.java
     *  抽象类 AbstractHeap.java
     *  二叉堆 BinaryHeap.java
 *  构建一个最小堆
 *  TOP K 问题

# 堆（Heap） #

## 堆的出现，思考？ ##

设计一种数据结构，用来存放整数，要求提供 3 个接口：

*  添加元素
 *  获取最大值
 *  删除最大值

用已学过的数据结构来对比一下时间复杂度：  
![在这里插入图片描述][20210310091940256.png]  
为了迎合此需求出现了一种新的数据结构 —— 堆：

*  获取最大值： O ( l o g n ) O(logn) O(logn)
 *  删除最大值： O ( l o g n ) O(logn) O(logn)
 *  添加元素： O ( l o g n ) O(logn) O(logn)

## 堆简介 ##

堆（Heap）是一种 树状 的数据结构，常见的堆实现有

*  二叉堆（Binary Heap，完全二叉堆）
 *  多叉堆（D-heap、D-ary Heap）
 *  索引堆（Index Heap）
 *  二项堆（Binomial Heap）
 *  斐波那契堆（Fibonacci Heap）
 *  左倾堆（Leftist Heap，左式堆）
 *  斜堆（Skew Heap）

堆的重要性质：任意节点的值总是  ≥ ≥ ≥ （  ≤ ≤ ≤ ）`子节点`的值

*  如果任意节点的值总是  ≥ ≥ ≥ `子节点`的值，称为：最大堆、大根堆、大顶堆
 *  如果任意节点的值总是  ≤ ≤ ≤ `子节点`的值，称为：最小堆、小根堆、小顶堆

堆中的元素必须具备可比较性（跟二叉搜索树一样）

注意：

*  × 没有【上一层节点的值，一定大于下一层节点的值】这一说法
 *  √ 只有任意节点的值，总是大于它的子节点

堆中的元素必须具备可比较性（跟二叉搜索树一样）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

# 二叉堆（Binary Heap） #

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆

鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
索引 i 的规律（n 是元素数量）

*  如果 i = 0，它是 根 节点
 *  如果 i > 0，它的 父 节点的索引为  f l o o r ( ( i − 1 ) / 2 ) floor( (i - 1) / 2 ) floor((i−1)/2)
 *  如果  2 i + 1 ⩽ n − 1 2 i + 1 ⩽ n − 1 2i\+1⩽n−1，它的左子节点的索引为  2 i + 1 2 i + 1 2i\+1
 *  如果  2 i + 1 > n − 1 2 i + 1 > n − 1 2i\+1>n−1，它无左子节点
 *  如果  2 i + 2 ⩽ n − 1 2 i + 2 ⩽ n − 1 2i\+2⩽n−1，它的右子节点的索引为  2 i + 1 2 i + 1 2i\+1
 *  如果  2 i + 2 > n − 1 2 i + 2 > n − 1 2i\+2>n−1，它无右子节点

## 获取最大值 ##

主要就是检测数组是否不能为空，为空则抛出异常。

public E get() {
        
    	emptyCheck();
    	return elements[0];
    }
    
    private void emptyCheck() {
        
    	if (size == 0) {
        
    		throw new IndexOutOfBoundsException("Heap is empty");
    	}
    }

## 最大堆 — 添加 ##

思路是：

*  将添加的节点放入数组最后（图中的 80 简称为 node）
 *  循环执行上滤操作(Sift Up)，即：
    
     *  如果 node > 父节点  
        与父节点交换位置
     *  如果 node <= 父节点，或者 node 没有父节点  
        退出循环
 *  时间复杂度： O ( l o g n ) O(logn) O(logn)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]

/**
     * 最大堆 — 添加
     */
    public void add(E element) {
        
    	// 检测传入的元素非空
    	elementNotNullCheck(element);
    	// 扩容操作，确保容量大于当前元素个数大小
    	ensureCapacity(size + 1);
    	// 将要添加的元素放到数组最后
    	elements[size++] = element;
    	// 上滤操作
    	siftUp(size - 1);
    }
    /**
     * 让index位置的元素上滤
     */
    private void siftUp(int index) {
        
    	E e = elements[index]; // 要添加的节点
    	while (index > 0) {
         // 直到比较到根结点
    		int pindex = (index - 1) >> 1; // 父节点索引
    		E p = elements[pindex]; // 添加节点的父节点
    		if (compare(e, p) <= 0) return;
    		
    		// 交换index、pindex位置的内容
    		E tmp = elements[index];
    		elements[index] = elements[pindex];
    		elements[pindex] = tmp;
    		
    		// 重新赋值index
    		index = pindex;
    	}
    }

## 最大堆 — 添加优化 ##

和上面的区别在于：

*  并不是每次节点的值 > 父节点的值就直接交换
 *  而是将新添加的节点备份，确定最终位置才放上去

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]

/**
     * 最大堆 — 添加
     */
    public void add(E element) {
        
    	// 检测传入的元素非空
    	elementNotNullCheck(element);
    	// 扩容操作，确保容量大于当前元素个数大小
    	ensureCapacity(size + 1);
    	// 将要添加的元素放到数组最后
    	elements[size++] = element;
    	// 上滤操作
    	siftUp(size - 1);
    }
    
    /**
     * 让index位置的元素上滤
     */
    private void siftUp(int index) {
        
    	E element = elements[index];
    	while (index > 0) {
        
    		// 父节点索引 = (子节点索引-1) / 2
    		int parentIndex = (index - 1) >> 1;
    		E parent = elements[parentIndex];
    		if (compare(element, parent) <= 0) break;
    		
    		// 将父元素存储在index位置
    		elements[index] = parent;
    		
    		// 重新赋值index
    		index = parentIndex;
    	}
    	elements[index] = element;
    }

## 最大堆 — 删除 ##

思路是：

*  用最后一个节点覆盖根结点
 *  删除最后一个节点
 *  循环执行下滤操作(Sift Down)，即：
    
     *  如果 node < 最大的子节点  
        与最大的子节点交换位置
     *  如果 node >= 最大的子节点，或者 node 没有子节点  
        退出循环
 *  时间复杂度： O ( l o g n ) O(logn) O(logn)
 *  交换位置的操作可以像添加那样进行优化  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]

/**
     * 最大堆—删除堆顶元素
     */
    public E remove() {
        
    	// 检测数组不能为空
    	emptyCheck(); 
    	// 获取数组最后元素的索引
    	int lastIndex = --size;
    	// 获取要删除元素的节点
    	E root = elements[0];
    	elements[0] = elements[lastIndex];
    	elements[lastIndex] = null;
    	
    	siftDown(0); // 下滤操作
    	return root;
    }
    /**
     * 让index位置的元素下滤
     */
    private void siftDown(int index) {
        
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 == 非叶子节点的数量 == floor(size/2)
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点
        while (index < half) {
        
            // 完全二叉树子节点有两种情况
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点
    
            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
        
                child = elements[childIndex = rightIndex];
            }
            if (compare(element, child) >= 0) break;
            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }

## replace ##

替换堆顶的元素

/**
     * 删除堆顶元素，同时添加一个元素
     *
     * @param element 添加的元素
     * @return 返回被删除的元素
     */
    @Override
    public E replace(E element) {
        
        elementNotNullCheck(element);
    
        E root = null;
        if (size == 0) {
        
            elements[0] = element;
            size++;
        } else {
        
            root = elements[0]; //记录堆顶元素
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

## 最大堆 – 批量建堆（Heapify） ##

批量建堆，有 2 种做法

*  自上而下的上滤
    
     *  上滤：当前节点与它父节点比较，若当前节点大于父节点，则与父节点交换位置（即上去）

*  自下而上的下滤
    
     *  下滤：当前节点与它子节点比较，若当前节点小于子节点，则与子节点交换位置（即下去）

### 自上而下的上滤 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

### 自下而上的下滤 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]

## 效率对比 ##

*  自上而下的上滤 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
 *  自下而上的下滤 时间复杂度： O ( n l o g k ) O(nlogk) O(nlogk)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]

# 二叉堆代码 #

## 堆的基本接口-Heap.java ##

public interface Heap<E> {
        
    
    	int size();	// 元素的数量
    	
    	boolean isEmpty();	// 是否为空
    	
    	void clear();	// 清空
    	
    	void add(E element);	 // 添加元素
    	
    	E get();	// 获得堆顶元素
    	
    	E remove(); // 删除堆顶元素
    	
    	E replace(E element); // 删除堆顶元素的同时插入一个新元素
    }

## 抽象类 AbstractHeap.java ##

@SuppressWarnings("unchecked")
    public abstract class AbstractHeap<E> implements Heap<E> {
        
    	protected int size;
    	protected Comparator<E> comparator;
    	
    	public AbstractHeap(Comparator<E> comparator) {
        
    		this.comparator = comparator;
    	}
    	
    	public AbstractHeap() {
        
    		this(null);
    	}
    	
    	@Override
    	public int size() {
        
    		return size;
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    	
    	protected int compare(E e1, E e2) {
        
    		return comparator != null ? comparator.compare(e1, e2) 
    				: ((Comparable<E>)e1).compareTo(e2);
    	}
    }

## 二叉堆 BinaryHeap.java ##

/**
     * 二叉堆（大顶堆）
     */
    @SuppressWarnings("unchecked")
    public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
        
        private E[] elements;
        private static final int DEFAULT_CAPACITY = 10;
    
        public BinaryHeap(E[] elements, Comparator<E> comparator) {
        
            super(comparator);
    
            if (elements == null || elements.length == 0) {
        
                this.elements = (E[]) new Object[DEFAULT_CAPACITY];
            } else {
        
                size = elements.length;
                int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
                this.elements = (E[]) new Object[capacity];
                for (int i = 0; i < elements.length; i++) {
        
                    this.elements[i] = elements[i];
                }
                heapify();
            }
        }
    
        public BinaryHeap(E[] elements) {
        
            this(elements, null);
        }
    
        public BinaryHeap(Comparator<E> comparator) {
        
            this(null, comparator);
        }
    
        public BinaryHeap() {
        
            this(null, null);
        }
    
        @Override
        public void clear() {
        
            for (int i = 0; i < size; i++) {
        
                elements[i] = null;
            }
            size = 0;
        }
    
        @Override
        public void add(E element) {
        
            elementNotNullCheck(element);
            ensureCapacity(size + 1);
            elements[size++] = element;
            siftUp(size - 1);
        }
    
        @Override
        public E get() {
        
            emptyCheck();
            return elements[0];
        }
    
        @Override
        public E remove() {
        
            emptyCheck();
    
            int lastIndex = --size;
            E root = elements[0];
            elements[0] = elements[lastIndex];
            elements[lastIndex] = null;
    
            siftDown(0);
            return root;
        }
    
        /**
         * 删除堆顶元素，同时添加一个元素
         *
         * @param element 添加的元素
         * @return 返回被删除的元素
         */
        @Override
        public E replace(E element) {
        
            elementNotNullCheck(element);
    
            E root = null;
            if (size == 0) {
        
                elements[0] = element;
                size++;
            } else {
        
                root = elements[0]; //记录堆顶元素
                elements[0] = element;
                siftDown(0);
            }
            return root;
        }
    
        /**
         * 批量建堆
         */
        private void heapify() {
        
            // 自上而下的上滤
    //		for (int i = 1; i < size; i++) {
        
    //			siftUp(i);
    //		}
    
            // 自下而上的下滤
            for (int i = (size >> 1) - 1; i >= 0; i--) {
        
                siftDown(i);
            }
        }
    
        /**
         * 让index位置的元素下滤
         *
         * @param index 索引
         */
        private void siftDown(int index) {
        
            E element = elements[index];
            int half = size >> 1;
            // 第一个叶子节点的索引 == 非叶子节点的数量 == floor(size/2)
            // index < 第一个叶子节点的索引
            // 必须保证index位置是非叶子节点
            while (index < half) {
        
                // 完全二叉树子节点有两种情况
                // index的节点有2种情况
                // 1.只有左子节点
                // 2.同时有左右子节点
    
                // 默认为左子节点跟它进行比较
                int childIndex = (index << 1) + 1;
                E child = elements[childIndex];
                // 右子节点
                int rightIndex = childIndex + 1;
                // 选出左右子节点最大的那个
                if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
        
                    child = elements[childIndex = rightIndex];
                }
                if (compare(element, child) >= 0) break;
                // 将子节点存放到index位置
                elements[index] = child;
                // 重新设置index
                index = childIndex;
            }
            elements[index] = element;
        }
    
        /**
         * 让index位置的元素上滤
         *
         * @param index
         */
        private void siftUp(int index) {
        
    //		E e = elements[index];
    //		while (index > 0) {
        
    //			int pindex = (index - 1) >> 1;
    //			E p = elements[pindex];
    //			if (compare(e, p) <= 0) return;
    //			
    //			// 交换index、pindex位置的内容
    //			E tmp = elements[index];
    //			elements[index] = elements[pindex];
    //			elements[pindex] = tmp;
    //			
    //			// 重新赋值index
    //			index = pindex;
    //		}
            E element = elements[index];
            while (index > 0) {
        
                int parentIndex = (index - 1) >> 1;
                E parent = elements[parentIndex];
                if (compare(element, parent) <= 0) break;
                // 将父元素存储在index位置
                elements[index] = parent;
                // 重新赋值index
                index = parentIndex;
            }
            elements[index] = element;
        }
    
        private void ensureCapacity(int capacity) {
        
            int oldCapacity = elements.length;
            if (oldCapacity >= capacity) return;
    
            // 新容量为旧容量的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
        
                newElements[i] = elements[i];
            }
            elements = newElements;
        }
    
        private void emptyCheck() {
        
            if (size == 0) {
        
                throw new IndexOutOfBoundsException("Heap is empty");
            }
        }
    
        private void elementNotNullCheck(E element) {
        
            if (element == null) {
        
                throw new IllegalArgumentException("element must not be null");
            }
        }
    
        @Override
        public Object root() {
        
            return 0;
        }
    
        @Override
        public Object left(Object node) {
        
            int index = ((int) node << 1) + 1;
            return index >= size ? null : index;
        }
    
        @Override
        public Object right(Object node) {
        
            int index = ((int) node << 1) + 2;
            return index >= size ? null : index;
        }
    
        @Override
        public Object string(Object node) {
        
            return elements[(int) node];
        }
    }

# 构建一个最小堆 #

实现最小堆不需要修改源代码，只需要在创建堆时，传入与最大堆比较方式相反的比较器即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]

# TOP K 问题 #

什么是 TopK 问题

*  从 n 个整数中，找出最大的前 k 个数（k << n）
 *  例如：从100万个整数中找出最大的100个整数

TopK 问题的解法之一：可以用数据结构 “堆” 来解决

如果使用排序算法进行全排序，需要  O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度

如果使用二叉堆来解决，可以使用  O ( n l o g k ) O(nlogk) O(nlogk) 的时间复杂度来解决

步骤：

*  新建一个小顶堆
 *  扫描 n 个整数
    
     *  先将遍历到的前 k 个数放入堆中
     *  从第 k+1 个数开始，如果大于堆顶元素，就使用 replace 操作  
        （删除堆顶元素，将第k+1个数添加到堆中）
 *  扫描完毕后，堆中剩下的就是最大的前 k 个数

本质：

因为是小顶堆，堆顶永远是最小的元素，只要发现插入的元素 大于 堆顶最小元素，就替换堆顶元素，

这样每次插入元素，都可以保证当前 k 个元素是最大的，所以只要扫描全部元素，即可以找出最大的 K 个元素

public static void main(String[] args) {
        
    	// 新建一个小顶堆
    	BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
        
    		public int compare(Integer o1, Integer o2) {
        
    			return o2 - o1;
    		}
    	});
    	
    	// 找出最大的前k个数
    	int k = 3;
    	Integer[] data = {
        51, 30, 39, 92, 74, 25, 16, 93, 
    			91, 19, 54, 47, 73, 62, 76, 63, 35, 18, 
    			90, 6, 65, 49, 3, 26, 61, 21, 48};
    	for (int i = 0; i < data.length; i++) {
        
    		if (heap.size() < k) {
         // 前k个数添加到小顶堆
    			heap.add(data[i]); // logk
    		} else if (data[i] > heap.get()) {
         // 如果是第 k + 1 个数，并且大于堆顶元素
    			heap.replace(data[i]); // logk
    		}
    	}
    	// O(nlogk)
    }

如果是找出最小的前 k 个数呢？

*  用大顶堆
 *  如果小于堆顶元素，就使用 replace 操作

[20210310091940256.png]: /images/20221023/8cf91aa8d597493f90b8940418c42af1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221023/0c5ff29d945341308c0760a40db408a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221023/073e9c8f0b054e7090ccebd7f0b034e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221023/5c997f2f11004244a2e8445b2d3aa023.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221023/e14e3cab6a474b8bb18995278740b810.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221023/9e64ec319e434f469245c7f54695ca9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221023/623f390ddc3c4dbb96a16667204a144f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221023/369058b45d534a62b70c2bde2fdaf140.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: /images/20221023/c3d87f49fd434d419f6ab3d702d1df14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: /images/20221023/0e71bb335df4475abceeab359642ee88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: /images/20221023/882daab34b5c4b8aa7c90a2ae89673ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: /images/20221023/c1fcb39e989a4f8fb85cd2aaa4a6c1dd.png