walker's code blog

coder, reader

翻转二叉树

最近在找工作,所以这些算法梗又出现在了我的阅读视野里,比如经典的homebrew作者吐槽的翻转二叉树的问题。

我本以为是根和叶节点倒转过来,原来是同层里面的左右翻转。

那么就是把左边换到右边,右边换到左边呗,可以考虑递归。我一直用一个原则理解递归,就是把命令传达下去(比如上面的左右互换,就完了),而不关心细节,只有最末端的那个大头兵才是真正做业务的人,写了一下,递归加业务也就4行代码:

具体到这个问题,就是我把left和right互换就是了 然后left和right你们做好自己的子级的互换,我不管,所以核心代码就一句 left, right = right, left,前面是为了稳妥,通过了之后,直接用python这种左右互换的特性,那就真是一句代码了:

def invertTree(self, root: TreeNode) -> TreeNode:
    if root is None:
        return None
    root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)
    return root

理解Core-Graphics的Clipping和填充模式

先来看一个例子

画一个箭头,其中箭尾有分叉,一般来说,是画一个三角,画一个矩形(实心矩形一般也直接用很粗的线条),最后再叠一个三角(with CGBlendModel.clear),这里就不多介绍了:

override func draw(_ rect: CGRect) {       
    let p = UIBezierPath()
    // shaft
    UIColor.yellow.set()
    p.move(to:CGPoint(100,100))
    p.addLine(to:CGPoint(100, 19))
    p.lineWidth = 20
    p.stroke()

    // point
    UIColor.red.set()
    p.removeAllPoints()
    p.move(to:CGPoint(80,25))
    p.addLine(to:CGPoint(100, 0))
    p.addLine(to:CGPoint(120, 25))
    p.fill()

    // snip
    p.removeAllPoints()
    p.move(to:CGPoint(90,101))
    p.addLine(to:CGPoint(100, 90))
    p.addLine(to:CGPoint(110, 101))
    p.fill(with:CGBlendMode.clear, alpha:1.0)
}

我们来看看clipping怎么用

  1. fill三角箭头(出于堆叠上目的可以最后画)
  2. 找到箭尾的三个顶点
    • boundingBoxOfClipPath来创建整个画板大小的矩形
    • 应用clipping把小三角挖掉

3,画一根黄色箭柄粗细的线(从底向上) * 因为小三角区域被clipping掉了,结果就成了图示的模样

override func draw(_ rect: CGRect) {
        // obtain the current graphics context
        let con = UIGraphicsGetCurrentContext()!

        // punch triangular hole in context clipping region
        con.move(to:CGPoint(x:90, y:100))
        con.addLine(to:CGPoint(x:100, y:90))
        con.addLine(to:CGPoint(x:110, y:100))
        con.closePath()
        // 添加整个区域为rect
        // 然后再clip设定为不渲染的区域
        // 后续的渲染全会避开这个区域
        // 我们后面把这个rect设为蓝色试试(顺便改为一个小一点的rect)
        con.addRect(con.boundingBoxOfClipPath)
        con.clip(using:.evenOdd)
//        con.fillPath()

        // draw the vertical line
        con.setStrokeColor(UIColor.yellow.cgColor)
        con.move(to:CGPoint(x:100, y:100))
        con.addLine(to:CGPoint(x:100, y:19))
        con.setLineWidth(20)
        con.strokePath()

        // draw the red triangle, the point of the arrow
        con.setFillColor(UIColor.red.cgColor)
        con.move(to:CGPoint(x:80, y:25))
        con.addLine(to:CGPoint(x:100, y:0))
        con.addLine(to:CGPoint(x:120, y:25))
        con.fillPath()
    }

能够完美run起来,但是我对clipping的机制还是有点不理解,一些关键点的讲解,和我的问题,一条条过:

  1. 我们用构建了箭尾的三角形,然后closePath,那是因为我们只画了两条线,如果事实上第三条线连回了原点,那么这个closePath就不需要了
  • (图一)演示了不close的话就直接只有两条线了
  1. 我想看看clipping到底发生了啥,于是注释掉了clip的那一行,得到了(图二)
  • 之所以长那样是因为随后设置了stroke的参数(20像素的黄色)
  • stroke时,画板上有三个元素:一个三角,一个矩形,一条线段,全部用20宽的黄线描边了,一切如预期
  1. 于是我尝试添加rect时只取了中间一小块,并涂成蓝色,不clip试试,得到(图三)。
  2. 知道了新rect的位置,把clip加回来,发现箭尾有了,箭头却没了(图四)
  3. rect与clip的关系已经出来了,尝试把红三角的y通通加50,移到了蓝矩形范围内,得到证明(图五)

那么clipping到底能对哪些起作用呢?是上面的rect吗?当然不是

在clip方法被调用的时候,画布里有多少封闭元素,就会被应用clip。由于我们选择的是evenOdd模式,那么就会简单计数,某像素覆盖奇数次显示,偶数次则不显示。

上例中,con.clip(using:)方法调用时,画布里有两个封闭元素,一个三角,一个矩形,三角包在矩形里,那么计数为2,就不予显示了。

事实上,判定奇偶的依据是该点向外做无限长的射线,判定有几条边与射线相交。同时,同样的设定可以用来解释.winding模式,即不但与相交的边有交,还与相交时,那条边是顺时针方向绘制的(+1)还是逆时针方向绘制的(-1),总结果为0则不填充。参考

那就玩一玩验证下吧

  1. 把矩形改成了圆圈,线宽也改小一点,得到(图一)绿色三角形是我后加的,因为被黄实线盖住了
  2. 再在里面添加了一个小圆,得到(图二)
  3. 这时候按照奇偶原则,小圆里的像素是偶数,而小圆里的三角则是奇数了,那么应该就只有大圆减掉小圆的部分,和小圆内的三角会被渲染了(图三),与预期一致

现在再来回顾书上先套一个画布大小的矩形,再画一个三角形,你大概应该知道目的了(凑奇偶),我们矩形区域过小时绘制不了红色三角,纯粹也是因为奇数,往下移到矩形区域内,立马变偶数了。(当然,要在原位置渲染我们可以先中止clip:con.resetClip()再绘图)

Programming iOS 14 - Threading

《Programming iOS 14: Dive Deep into Views, View Controllers, and Frameworks》第25章


Thread

Thread在开发过程中基本上线程是隐形的,你感知不到,因为大多数情况下,程序只(需要)跑在主线程上,这是没有问题的:

  • 你的代码事实上执行得非常快,你感知不到
  • 响应逻辑过程锁死UI,是安全的操作

原生的后台线程:

  • 动画:The Core Animation framework is running the animation and updating the presentation layer on a background thread.
  • 网络:A web view’s fetching and loading of its content is asynchronous
  • 影音:Sounds are played asynchronously. Loading, preparation, and playing of movies happens asynchronously.
  • 存盘:UIDocument saves and reads on a background thread.

但所有的complete functions / delegations / notification 都是在主线程被调用的

多线程的问题

  • 调用时机/顺序不可控,次数也不可控,随时可能被执行
  • 数据的线程安全,不得不借助“锁”的机制来保证(race condition)
    • a lock is an invitation to forget to use the lock, or to forget to remove the lock after you’ve set it.
  • The lifetime of a thread is independent of the lifetimes of other objects in your app.
    • 一个对象的退出不能保证有后台线程将来会调用它 -> 闪退或Zombie
  • Hard to debug.

XCode对debug的支持:

  • Debug navigator
  • NSLog / os_log / Logger outputs
  • Instruments > Time Profiler
  • Thread Sanitizer, Main Thread Checker (项目配置 > Diagnostics)

执行后台线程的方法:

Manual Threading

performSelector(inBackground:with:)

  • 只能传一个参数,多个参数要打包
  • 手动管理内存 -> wrap every thing in an autorelease pool
func drawThatPuppy () {
        self.makeBitmapContext(size:self.bounds.size)
        let center = self.bounds.center
        // 这里打包参数为一个字典
        let d : [AnyHashable:Any] =
            ["center":center, "bounds":self.bounds, "zoom":CGFloat(1)]
        self.performSelector(inBackground: #selector(reallyDraw), with: d)
    }
// trampoline, background thread entry point
@objc func reallyDraw(_ d: [AnyHashable:Any]) {
    // 手动控制内存
    autoreleasepool {
        self.draw(center: d["center"] as! CGPoint,
            bounds: d["bounds"] as! CGRect,
            zoom: d["zoom"] as! CGFloat)
        // 手动回调主线程
        self.performSelector(onMainThread: #selector(allDone), with: nil,
            waitUntilDone: false)

}
// called on main thread! background thread exit point
@objc func allDone() {
    self.setNeedsDisplay()
}

即便如此,还是没有解决不同线程使用同一个实例变量(如bitmapContext)造成程序非常脆弱的问题,得进一步使用lock等机制。

Operation

  • thread封装成task,表示成Operation 通过 OperationQueue来操作。
  • 回调机制变成了通知机制(或KVO
let queue : OperationQueue = {
    let q = OperationQueue()
    // ... further configurations can go here ...
    return q
}()

func drawThatPuppy () {
    let center = self.bounds.center
    // 也可以用 BlcokOperation
    // 来执行你的耗时操作
    let op = MyMandelbrotOperation(
        center: center, bounds: self.bounds, zoom: 1)
    // 通知/回调
    NotificationCenter.default.addObserver(self,
        selector: #selector(operationFinished),
        name: MyMandelbrotOperation.mandelOpFinished, object: op)
    // 结合起来
    self.queue.addOperation(op)
}

而一个Operation子类包含两个部分:

  1. A designated initializer
    • 你可以把需要的参数设计成对应的属性,并初始化好它
  2. A main method
    • 耗程序真正执行的地方,OperationQueue执行到这个Operation的时候就会被自动执行
class MyMandelbrotOperation: Operation {
    static let mandelOpFinished = Notification.Name("mandelOpFinished")

    // 1. params -> arguments
    private let center : CGPoint
    private let bounds : CGRect
    private let zoom : CGFloat
    private(set) var bitmapContext : CGContext! = nil  // 封装成了类属性,不再线程共享
    init(center c:CGPoint, bounds b:CGRect, zoom z:CGFloat) {
        self.center = c
        self.bounds = b
        self.zoom = z
        super.init()
    }

    // 1.1 logic
    let MANDELBROT_STEPS = 100
    func makeBitmapContext(size:CGSize) {
        // ... same as before
    }
    func draw(center:CGPoint, bounds:CGRect, zoom:CGFloat) {
        // ... same as before
    }

    // 2. main
    override func main() {
        // 首先要检查isCancelled
        guard !self.isCancelled else {return}
        self.makeBitmapContext(size: self.bounds.size)
        self.draw(center: self.center, bounds: self.bounds, zoom: self.zoom)
        if !self.isCancelled {
            // 完成通知,也可以用KVO机制
            // 主线程接收到后要立即处理,因为OpearationQueue将会立即释放这个Operation
            // 此外,接收通知可能也不在主线程,-> GCD
            NotificationCenter.default.post(
                name: MyMandelbrotOperation.mandelOpFinished, object: self)
        }
    }
}

// 3. observer
// 就是前面在主线程里注册监听消息的方法
// warning! called on background thread
@objc func operationFinished(_ n:Notification) {
    if let op = n.object as? MyMandelbrotOperation {
        // 1. 主线程(GCD)
        DispatchQueue.main.async {
            // 2. 移除通知监听
            NotificationCenter.default.removeObserver(self,
                name: MyMandelbrotOperation.mandelOpFinished, object: op)
            self.bitmapContext = op.bitmapContext  // 传回这个之前是线程共享的变量
            self.setNeedsDisplay()
        }
    } 
}

注意bitmapContext这个之前主线程设置,然后后台线程共享的变量,现在由Operation这个类自己持有,结束时才赋值回主线程。

此外,还能限制并发数量:

let q = OperationQueue()
q.maxConcurrentOperationCount = 1

This turns the OperationQueue into a serial queue.

最后,解决最后一个问题,即你的调用者都没了,比如ViewController没了,调用者没了,后台任务也理应取消(下载、存盘类不需要UI交互的除外)

deinit{
    self.queue.cancelAllOperations()
}

至此,前面提到的一些多线程会带来的问题如调用时机和数量不可控,跨线程数据安全,以及生命周期等问题,Operation都完美解决并封装了。

设置优先级,QoS, 依赖等一些进阶示例:

let backgroundOperation = NSOperation()
backgroundOperation.queuePriority = .Low
backgroundOperation.qualityOfService = .Background

let operationQueue = NSOperationQueue.mainQueue()
operationQueue.addOperation(backgroundOperation)

// dependence
let networkingOperation: NSOperation = ...
let resizingOperation: NSOperation = ...
resizingOperation.addDependency(networkingOperation)

let operationQueue = NSOperationQueue.mainQueue()
// 虽然resizing添加了network为依赖,但是还是需要全部加到队列里
// 不要以为加了尾部operation就能把依赖全加进去
operationQueue.addOperations([networkingOperation, resizingOperation], waitUntilFinished: false)

Grand Central Dispatch

可以认为GCD是更底层的Operation,它甚至直接嵌入了操作系统,能被任何代码执行而且非常高效。调用过程也与Operation差不多:

  • 表示一个task
  • 加入一个queue
    • GCD Queue也被表示成了dispatch queue
    • a lightweight opaque pseudo-object consisting essentially of a list of functions to be executed.
    • 如果自定义这个queue,它默认状态下是serial queue
let MANDELBROT_STEPS = 100
var bitmapContext: CGContext!
let draw_queue = DispatchQueue(label: "com.neuburg.mandeldraw")

// 改造一个返回前述跨线程变量的方法
func makeBitmapContext(size:CGSize) -> CGContext {
    // ... as before ...
    let context = CGContext(data: nil,
        width: Int(size.width), height: Int(size.height),
        bitsPerComponent: 8, bytesPerRow: bitmapBytesPerRow,
        space: colorSpace, bitmapInfo: prem)
    return context!
}
// 相应方法增加这个context参数,而不是从环境里取
func draw(center:CGPoint, bounds:CGRect, zoom:CGFloat, context:CGContext) {
        // ... as before, but we refer to local context, not self.bitmapContext
}

// 剩下的,一个block搞定:
// UI触发的事件
func drawThatPuppy () {
    let center = self.bounds.center
    let bounds = self.bounds
    self.draw_queue.async {
        // 下面两行代码虽然用到了self,但是它们没有改变任何属性,是线程安全的
        let bitmap = self.makeBitmapContext(size: bounds.size)
        self.draw(center: center, bounds: bounds, zoom: 1, context: bitmap)
        DispatchQueue.main.async {
            self.bitmapContext = bitmap
            self.setNeedsDisplay()
        }
    } 
}

可以看到,相比Operation把代码结构都改了,GCD几乎只是包了一层block,代码变动非常少。(唯一的发动就是把所有执行代码的变量都需要通过参数机制传进去)。

同时, center, bounds等参数,直接从环境里取,这是block机制带来的便利;同样的机制也被用在了线程共享的变量传回主线程时,因为对第二层block而言,第一层block就是它的higher surrounding scope,是能看到它的bitmap变量的。 -> 我们并没有从头到尾retrive一个self.bitmap变量,也就不存在data sharing。

不像Operation把耗时操作写在别处,GCD的方式易读性更高。

除了有.async(execute:),还有asyncAfter(deadline:execute:)sync(execute:),望文生义,就不多介绍了。

Dispatch Groups

group提供了监听(wait)一组后台线程全部执行结束的功能:

let outerQueue = DispatchQueue(label: "outer")
let innerQueue = DispatchQueue(label: "inner")
let group = DispatchGroup()
outerQueue.async {
    let series = "123456789"
    for c in series {
        group.enter()  // flag 1
        innerQueue.asyncAfter(
            deadline:.now() + .milliseconds(Int.random(in: 1...1000))) {
                print(c, terminator:"")
                group.leave() // flag 2
        } 
        group.wait()  // 一旦加了这句话,这9个线程就变成线性的了,注释掉,就是9个线程随机先后执行
    }
    // 可见这个notify等同于wait_all
    // 当enter次数与leave次数一致时触发
    group.notify(queue: DispatchQueue.main) {
        print("\ndone")
    } 
}

One-Time Execution

Objective-C中实现单例的dispatch_once其实就是GCD的内容,而在Swift中这个方法就没有了,也没用GCD去实现了:

let globalOnce : Void = {
        print("once in a lifetime") // once, at most
}()

这个print只会打印一次。而如果是用在对象中,可以声明为lazy

class ViewController: UIViewController {
        private lazy var instanceOnce : Void = {
            print("once in an instance") // once per instance, at most
        }()
// ... }

instanceOnce这个变量也只会初始化一次。

Bonus

// 并发
let queue = DispatchQueue(label: "queue", attributes: .concurrent)
// 条件, check the queue
dispatchPrecondition(condition: .onQueue(self.draw_queue))

App Backgrounding

  • 应用进入后台时,iOS系统会给应用小于5秒的时间来结束当前的任务
  • 可以用UIApplication.shared.beginBackgroundTask(expirationHandler:)来申请更长的时间(不超过30秒),返回一个identifier
    • expirationHandler是一个超时还没处理完的话,系统会调的方法,
  • 任务执行完后需要调用UIApplication.shared.endBackgroundTask(_:)方法来结束后台时间的申请
    • expirationHandler里同样需要显式endBackgroundTask
    • 所以正常方法体和超时方法体都会有endBackgroundTask的调用

把这个特性直接封装到一个operation里去:

class BackgroundTaskOperation: Operation {
    var whatToDo : (() -> ())?
    var cleanup : (() -> ())?
    override func main() {
        guard !self.isCancelled else { return }
        var bti : UIBackgroundTaskIdentifier = .invalid
        bti = UIApplication.shared.beginBackgroundTask {
            self.cleanup?()
            self.cancel()
            UIApplication.shared.endBackgroundTask(bti) // cancellation
        }
        guard bti != .invalid else { return }
        whatToDo?()
        guard !self.isCancelled else { return }
        UIApplication.shared.endBackgroundTask(bti) // completion
    }
}

// 调用
let task = BackgroundTaskOperation()
task.whatToDo = {
    ...
}
myQueue.addOperation(task)

这样,

  • 正常情况下会执行whatToDo()
  • 如果应用被挂到后台,因为注册过后台任务,有小于30秒的时间跑完任务
  • 如果顺利跑完,你把应用切到前台,会发现UI已经更新了
  • 超时也没跑完,就会进入超时的block里去取消任务了,UI上也得不到结果

最后,要知道所谓的申请时长,并不是在didEnterBackground之类的方法里去做的,而是做任务的时候就直接注册了,是不是很麻烦?

Background Processing

相比向系统申请少得可怜的后台挂起时间,iOS 从13开始引入了后台任务机制,方便你执行一些用户不需要感知的任务,比如下载,或数据清理:

  • 路径:target > Signing & Capabilities > Background processing
  • use Background Task framework, need to import BackgroundTasks
  • Info.plist > add "Permitted background task schedule identifiers" key (BTTaskSchedulerPermittedIdentifiers), 任意标识字符串,比如反域名
  • appDelegate里面去实现需要后台执行的方法

涉及到两个类:

  • BGProcessingTaskRequest
    • didEnterBackground方法里调用
    • 需要match plist.info里的id
    • 注册是否通电/有网/延迟执行(ExternalPower / Network / earliestBeginDate)
  • BGTaskScheduler
    • application(_:didFinishLaunchingWithOptions:)里执行
    • register(forTaskWithIdentifier:using:launchHandler:)方法
      • id: matching plist.info
      • using: dispatch queue
      • handler: BGTask object
    • BGTask的超时方法里,和正常执行的代码里,均需调用setTaskCompleted(_:bool)方法
let taskid = "com.neuburg.matt.lengthy"
func application(_ application: UIApplication,
    didFinishLaunchingWithOptions launchOptions:
    [UIApplication.LaunchOptionsKey : Any]?) -> Bool {
}
// let v = MyView()
let ok = BGTaskScheduler.shared.register(
    forTaskWithIdentifier: taskid,
    using: DispatchQueue.global(qos: .background)) { task in
        task.expirationHandler = {
            task.setTaskCompleted(success: false)
        }
        //... my task logic
        task.setTaskCompleted(success: true)
    }
    // might check `ok` here
    return true
}

func applicationDidEnterBackground(_ application: UIApplication) {
    // might check to see whether it's time to submit this request
    let req = BGProcessingTaskRequest(identifier: self.taskid)
    try? BGTaskScheduler.shared.submit(req)
}

Debug

  1. 打满print和断点
  2. 设备上,把应用送到后台再拉到前台
  3. Xcode上暂停app
  4. (lldb) e -l objc -- (void)[[BGTaskScheduler sharedScheduler] _simulateLaunchForTaskWithIdentifier:@"my_id"] 模拟launching
    • (lldb) e -l objc -- (void)[[BGTaskScheduler sharedScheduler] _simulateExpirationForTaskWithIdentifier:@"my_id"] 模拟超时
  5. 控制台输入continue, 运行task function
  6. task.setTaskComplete(success: true) 被调用,控制台输出:“Marking simulated task complete,”

BGAppRefreshTaskRequest

not mentioned

数据结构篇九:Indexed Priority Queue

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Indexed Priority Queue

  • a traditional priority queue variant
  • top node supports quick update and deletions of key-value paris

观察这个图,数据是Anna, Bella...等等,

  • 首先,为这一堆数据进行任意排序,得到一堆索引(0,1,...)
  • 然后组一个binary heap,这样每个元素又获得一个索引,就是在heap上的序号(Position Map

通过两组索引迅速找到key(就是人名)在堆中的位置,比如:

  • George,ki = 6, pm = 1
  • kelly, ki = 10, pm = 10
  • ...

现在能迅速找到数据源在堆上的位置了,那么如果反过来呢?比如堆上索引3是数据源的谁?

  • pm = 3 -> ki = 8 -> Issac BINGO!!!

但神奇的事发生了,有人希望复用ki这个自然数序列(闲的蛋疼?),于是多做了一个数组,把ki定义为heap上的索引,与元素原来的ki进行映射(Inverse Map):IM

可以看到,这张图上张个ki到im的映射,与pm到ki的映射其实是一样的,也就是说重定义了一下,并没有引入新的东西。(pm表里找到3,对应的第一行ki表里就是8)

这个时候,我们直接用ki的3就能找到im的8,继而找到数据源的Issac了。

Insertion

上面的数组,我们往里面添加第12条数据试试:

  • {ki:12, pm: 12, im:12, value:2}
  • 显然违反了binary heap的 invariant,向上冒泡,也就是跟{ki:12, pm:5, im:2, value:4}的节点互换
  • 此时,数据源肯定不会变,但是节点变了,pm的值就要交换(5, 12 互换)
  • pm变了,把pm当成ki的映射表im也要变(12, 11互换)

仔细观察图片,搞清楚第一行ki在两次互换时的身份就明白了

  • pm的互换是直观的,就是节点的位置
  • 知道pm互换的依据后(2,5),在第一行找2,5对应的im值互换,因为在这个映射里,相当于pm与原ki的映射,pm此时是(2,5)了。

同样逻辑继续冒泡就是了。

pseudo code:

# Inserts a value into the min indexed binary 
# heap. The key index must not already be in 
# the heap and the value must not be null. 
function insert(ki, value):
    values[ki] = value
    # ‘sz’ is the current size of the heap
    pm[ki] = sz  # 对应上图,意思就第一行索引器是ki
    im[sz] = ki  # 对应上图,意思就是一行索引器是pm
    swim(sz)     # 这里传进去的pm,即heap上节点的索引
    sz = sz + 1  # 添加成功,size加1

理论上,添加元素到最后一个, sz和ki应该是相等的(因为都是尾巴上)

# Swims up node i (zero based) until heap 
# invariant is satisfied.
function swim(i):
    # 比父节点小就冒泡,注意入参i是节点上的索引,即pm
    for (p = (i-1)/2; i > 0 and less(i, p)): 
        swap(i, p)  # 所以这里传的也是pm
        i=p
        p = (i-1)/2

function swap(i, j): 
    # 我们交换了节点,需要交换pm表里的值,和im表里的值
    # 交换pm的值需要数据源的索引,即ki,而ki能从im表里用pm算出来
    # 所以ki = im[pm] 这里i,j是pm,所以im[i]自然就是i对应ki
    # pm[ki]当然就是pm[im[i]]了:
    pm[im[j]], pm[im[i]] = j, i
    im[i], im[j] = im[j], im[i]

function less(i, j):
    return values[im[i]] < values[im[j]]

还是那句话,理解清楚那三行映射表里第一行的动态含义,就不会有问题。

  • pm表要key index来索引
  • im表要node index来索引

在操作时,只需要知道传入的是哪种索引,及时转化就行了。

有了索引,lookup的时间复杂度就是常量时间了:O(1)

Polling and Removals

没有什么特殊的,仍然是找到节点,与最后一个交换,移除最后一个节点,然后再看最后一个在堆里是上升还是下降. 仍然是记得每一步交换,相应的几个索引值也需要随之交换.(polling 其实就是移除第1个节点,本质上还是 removal)

pseudo code

# Deletes the node with the key index ki
# in the heap. The key index ki must exist 
# and be present in the heap.
function remove(ki):
    # 注意,这里送进来的是ki,而不是node index(pm)
    # 说明业务需求一般是操作数据源,而不是操作堆
    i = pm[ki]    # 转成节点索引
    sz = sz - 1   # 与最后一个元素交换,用size来做节点索引

    # 下面三个子函数送入的就是节点索引了
    swap(i, sz) 
    sink(i)
    swim(i)

    values[ki] = null  # 数据源对应的值置空,所以用ki
    pm[ki] = -1        # 数据源对应的节点置空,所以用ki
    im[sz] = -1        # 反查表用节点索引,此处size就是最后一个节点的索引

sink pseudo code

# Sinks the node at index i by swapping 
# itself with the smallest of the left 
# or the right child node.
function sink(i):
    # 这是堆操作,传入的索引也是节点索引,没问题
    # sink是下沉,但不是跟BTS一样找左侧最大右则最小那种直接换
    # 而是一层层往下换
    # 即一次while只跟左右子级比大小,确实比子级还小的话,就替换,然后再跟下一层比较
    while true:
        # 利用二叉树特性算出子节点
        # 默认左边最小,然后再看右边是不是更小
        left =2*i+1
        right = 2*i + 2
        smallest = left
    # 右边不越界,且小于左边,就设右边
    if right < sz and less(right, left):
        smallest = right
    # 左侧都越界了,或已经比最小值大了,说明不需要下沉了
    if left >= sz or less(i, smallest):
        break
    # 只要没有break,说明能交换,然后把交换后的作为下一个循环的起点
    swap(smallest, i)
    i = smallest

Updates

更新节点要简单的多:

  • 用ki找到value,把值更新
  • 然后根据新value实际情况上浮或下沉
# Updates the value of a key in the binary 
# heap. The key index must exist and the
# value must not be null.
function update(ki, value):
    i = pm[ki]
    values[ki] = value
    sink(i)
    swim(i)

Decrease and Increase key

不好说,先看代码吧:

# For both these functions assume ki and value 
# are valid inputs and we are dealing with a
# min indexed binary heap.
function decreaseKey(ki, value):
    if less(value, values[ki]): 
        values[ki] = value 
        swim(pm[ki])

function increaseKey(ki, value): 
    if less(values[ki], value):
        values[ki] = value 
        sink(pm[ki])

代码里是跟一个固定值比较,只要ki对应的值比它大(desreaseKey)或小(increaseKey),就用这个固定值来替换它,并且在value改变后根据实际情况上浮或下沉。

数据结构篇八:Balanced Binary Search Trees(BBST)

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Balanced Binary Search Trees (BBST)

  • 满足low (logarithmic) height for fast insertions and deletions
  • clever usage of a tree invairant and tree rotation

AVL Tree

一种BBST,满足O(log n)的插入删除和查找复杂度,也是第一种BBST,后续出现的更多的:2-3 tree, AA tree, scapegoat tree, red-black tree(avl的最主要竞争对手)

能保持平衡的因子:Balance Factor (BF)

  • BF(node) = H(node.right) - H(node.left)
  • H(x) = height of node = # of edges between (x, furthest leaf)
  • 平衡就是左右平均分配,所以要么均分,要么某一边多一个,BF其实就是(-1, 0, 1)里的一个了 <- avl tree invariant

一个node需要存:

  • 本身的(comparable) value
  • balance factor
  • the height of this node
  • left/right pointer

使树保持左右平衡主要是靠rotation,极简情况下(三个node),我们有两种基本情况(left-left, right-right),有其它情况就旋转一次变成这两种情况之一:

Insertion

一次插入需要考虑的是,插在哪边,以及插入后对bf, height和balance的破坏

其中修复平衡就是上图中几个基本结构的转换

Removal

avl树就是一棵BST,删除节点分两步:

  1. 按照bst的方法查找节点,即小的在左边找,大的在右边找
  2. 也按bst的原则删除元素,即找到元素后,把左边的最大值或右边的最小值拿过来补上删除的位置
  3. 这一步是多出来的,显然是要更新一下节点的bf和height,及重新balance一次了。

前两部分参考BST一章,流程伪代码:

function remove(node, value): ...
    # Code for BST item removal here
    ...
    # Update balance factor
    update(node)
    # Rebalance tree
    return balance(node)

数据结构篇七:Suffix Array, Longest Common Prefix (LCP) array

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Suffix Array

  • 字符串的所有子字符串后缀组成数组
  • 对子串根据首字母进行排序
  • 排序后原有的index就被打乱了
  • 这个乱序的indices就是Suffix Array

做尾缀子串的时候通常是从单个字母开始越找越多,这就有了一个原生顺序,然后用首字母排序后,这个顺序就被打乱了

提供了一种compressd representation of sorted suffixes而无需真的把这些子串存起来。

  • A space efficient alternative to a suffix tree
    • a compressd version of a trie?

能做所有suffix tree能做的事,并加添加了Longest Common Prefix(LCP) array

Longest Common Prefix (LCP) array

继续上面的Suffix Array,字母排序后,我们一个个地用每一个元素同上一个元素比,标记相同前缀的字母个数,这个数字序列就是LCP

比如adc, adfgadc, 前缀ab是相同的,那就是2。

第一个元素没有“上一个”去比,所以LCP数组第1位永远是0?(是的,其实是undefined,但一般设0)

衡量的是相邻的suffix array元素的前缀间有多少个字母相同。

当前也可以和下一个元素比(这样最后一个元素的LCP肯定是0了,原理同上)

Find unique substrings

找到(或计数)一个数组的所有(不重复的)子元素。可以逐个substring遍历,$O(n^2)$,下面看看更快也更省空间的LCP方案。

找“AZAZA”的不重复子串: A,AZ,AZA,AZAZ,AZAZA,Z,ZA,ZAZ,ZAZA,A,AZ,AZA,Z,AZ,A,把重复的标注了出来。 LCP是这样的: LCP|Sorted Suffixes| -|- 0|A 1|AZA 3|AZAZA 0|ZA 2|ZAZA

我们知道第一列指的是“重复个数”,也就是说,如果按我们手写的那样去遍历,至少有这么多重复的子串,重复的既是“个数”,也是“组合方式”。

所以如果我们只需要计数的话,把右边的数出来就知道有会有多少个重复的了,此例为6.

$$\tt unique\ count = \underbrace{\frac{n(n+1)}{2}}_{substr\ count} - \underbrace{\sum_{i=1}^n LCP[i]}_{duplicates}$$

这是LCP的应用之一,利用了LCP本身就是在数重复次数的特征。

K common substring problem

n个字符串,找出一个子串,它至少是k个字符串的子串,求最大子串。$2\leq k \leq n$

即如果有k=2,那么这个子串只需要是其中两个的子串就行了,如果k=n,那么就需要是每一个字符串的子串。

直接上图

  • 图1演示k=3时,找到了ca,即3个串里都有的是ca
  • 图2演示k=2时,找到了bca,即bca存在2个串里
  • 图3演示的是用了size=4的滑窗才包含了3个字符串,以及最大匹配是AG

步骤:

  1. 首先,用几个分隔符把字符串拼接起来
    • 分隔符字符串里不会出现
    • 分隔符的排序要小于所有字符
  2. 图中染色的依据是prefix是哪个串里的就染成什么颜色
  3. 开始滑窗比较
    • 滑窗必须要能包含k种颜色
    • 所以滑窗大小不是固定的,有时候相邻几个都是来自同一个字符串
    • 滑窗里除0外的最小值,就是符合条件的最大共同长度,如图3,最大匹配长度是2
    • 课程里动画演示滑窗其实不是用滑的,而是用的爬行
      • 即下界往下,包含了所有颜色之后,上界也往下,这样蠕行前进,每一步判断滑窗里的内容
  4. 额外需要一个hash table来保存切片与颜色的映射关系。
    • 如果是例子这么简单,我可以直接检查第一个出现的分隔符,是#就是绿色,出现$就是蓝色,%就是红色

核心就是:

  • 取子串是从后向前取的
  • 但比较是从前向后比的
  • 前面的元素可能来自任何一个子串(只要足够长)
  • 从前面排序,客观上就把来自不同字符串的相同字母打头的子串给排到一起了

这就是为什么在Suffix Array的内容里面出现Longest Common Prefix的内容的原因了.

聪明。

Longest Repeated Substring (LRS)

这个比暴力遍历要简单太多,直接找LCP最大值即可

数据结构篇六:Fenwick Tree (Binary Indexed Tree)

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Fenwick Tree (Binary Indexed Tree)

树状数组

Motivation

  • 计算数组里任意连续片段的和,最直观的方案当然是累加:线性时间O(n)
  • 但是如果你有一个记录了每个节点到当前位置时的累加和的数组(prefix sum),立刻变成了常量时间
  • 问题是更新数据变成了线性时间(后续所有的求和都要改一遍)
    • great for static arrays

所以引入了: Fenwick Tree is an efficient data structure for performing range/point queries/updates.(即在上面的动机上,还考虑了update的效率)

前面的例子在update时效率不高,所以Fenwick Tree用了一种聪明的方式,不是累加所有的值,而是分段累加,具体实现看下图:

  • 把索引值用二进制表示
  • LSB的解释看图,实际应用上,就是看从低位到高位第一个1的右边有几个0,假设为n
  • 那么该cell上存的值就是前$2^n$个cell的值的和

图中例子是索引10,不直观,我们换成12, 二进制是1100, 最右边有2个零,那么它保存它$2^2=4$个位置的和。 也就是说,如果你要求和,如果用了cell 12位置的值的话,至少可以省掉3次累加。

当然,它还有更牛逼的特性,结合range query一起来看吧:

蓝线表示的是当然位置上累加了前几个位置的值,已经很有规律了

假如计算前11个值的和,过程是:

  1. 11的索引是1011,右边没有0,所以当前的和为A[11]
  2. 根据$2^0$来移位,来到10。
    • 右边一个0,所以它管$2^1$个presum,目前A[11] + A[10]
    • 下一个索引自然要减2了,来到8
  3. 8是1000,3个零,所以它存了$2^3=8$个值的和,那就是全部了

所以:sum = A[11] + A[10] + A[8]

  • 心算sum(0,7)巩固一下
  • 用sum(11,15)演示子区间,其实就是多减1次,至于是减到10还是减到11,看描述,比如这里11是要参与计算的,那就是把前10个减掉就行了。

上面演示的都是worst的情况,即首位为1,除了这种情况,别的位都至少存了前$2^n$个元素的值(比如16,直接得到16个元素的和)

这里都没讲你是怎么做这个tree的,而是怎么使用它。先弄清楚使用场景再谈构建。

Point Update

复习一下LSB,虽然可以直接数最右边的零的个数,但数学其实是:

  • 13 = 1101 ($2^3 + 2^2 + 2^0 \Rightarrow 10^3 + 10^2 + 10^0 $)
  • 减去最右边的1和0 => 1100 ($2^3+2^2=12$) 所以下一个数是12
  • 减去最右边的1和0 => 1000 就是8了
  • 再减就是0了

而按$2^n$来计算个数的话就是这样的:

  • 13 = 1101, 没有0,就是移1位,变成12
  • 12 = 1100, 2个0, 就是移4位,变成8
  • 8 = 1000, 3个0, 移8位,变成0

现在来讲update,前面知道,update会级联影响到所以把该cell考虑进去的节点,因此,它需要反着往上找(极端情况当然是找到最后一个元素,通常这个元素就是整个数组的值,所以任何元素的更改,肯定都会影响到它)

前面找下一个节点用的是减法,现在就要用加法了,比如我更新了cell 9, 用以上两种任意一种方法来计算:

  • $9 = 2^3 + 1 \Rightarrow 10^3 + 1 = 1001, +1 = 1010 = 10$
  • 1010 + 10 = 1100 = 12
  • 1100 + 100 = 10000 = 16 到顶了,

所以需要把9, 10, 12, 16分别应用这个point的更新,也就是说只有这几个cell把9计算进去了。

当然,可以看一下左边的示意图,更直观

function add(i, x): 
    while i < N:
        tree[i] = tree[i] + x 
        i = i + LSB(i)

代码非常简单,就是不断通过LSB找下一个位置去更新就行了。

Construction

现在来讲构建

function construct(values): N := length(values)
    # Clone the values array since we’re # doing in place operations
    tree = deepCopy(values)
    for i = 1,2,3, ... N:
        j := i + LSB(i)
        if j < N:
            tree[j] = tree[j] + tree[i]
    return tree

几乎就一句话,就是把元素按原数据摆好(即不加别的节点)后,每次找到当前元素影响的上一级(不再向上冒泡)

  • 比如1,把1算进去的有2,虽然上面还有4, 8, 16,但只把1更新到2
  • 到2的上一级是4 (2 + lsb(2) = 4), 把节点2的现值(已经加了节点1)加到4去
  • 所以核心算法始终只有两个变量,i,j代表最近的包含关系

一些算法换成位运算

  • lsb(i): i & -i
  • i -= lsb(i) => i &= ~lsb(i)

数据结构篇五:Hash Tables

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Hash Tables

  • key-value pair
  • using Hashing technique
  • often used tracking item frequencies

what's hash function?

  • maps a key x to a whole number in a fixed range.
    • e.g. $H(x) = (x^2 - 6x + 9) % 10$ maps (0, 9)
    • 这个方程会为不同的x产生一样的y -> hash collision
  • can hash arbitrary objects like string, list, tuple...
  • must be deterministic(确定的x产生确定的y)
    • 因此key的应该是immutable的类型

关键词是range,你设计的function总要mod一下,将结果限制在一个范围内。这里你应该暂时能推测出hashtable的key可能就是数字吧?

hash collision

  • separate chaining

用一种数据结构(通常是链表)保留所有冲突的值

  • open addressing

为冲突的值选择一个offset(地址/值)保存 -> probing sequence P(x)

不管是怎么解决冲突,worst的情况下,hash table的操作时间也会由O(1)变成O(n)

怎么用HT来查找呢?不是把hash后的结果拼到原数据上,而是每次查询前,对key进行一次hash function,就能去查询了。

Open Addressing

probing sequences

  • linear probing: P(x) = ax + b
  • quadratic probing: p(x) = $ax^2 + bx + c$
  • double hashing: p(k, x) = $x * H_2(k)$ 双重hash
  • pseudo random number generator: p(k, x) = x * rng(H(k), x) 用H(k)(即hash value)做种的随机数

总之就是在这样一个序列里找下一个位置

假设一个table size 为N的HT,使用开放寻址的伪代码:

x = 1
keyHash = H(k)   # 直接计算出来的hash value
index = keyHash  # 偏移过后存在HT里的index

while table[index] != None:
    index = (keyHash + P(k, x)) % N  # 加上偏移,考虑size(N)
    x += 1 # 游标加1

# now can insert (k,v) at table[index]

Chaos with cycles

Linear Probling (LP)

LP中,如果你运气不好,产生的序列的下一个值永远是occupied的状态(一般是值域小于size),就进入死循环了。

假设p(x) = 3x, H(k) = 4, N = 9 那么H(k)+P(x) % N 只会产生{4,7,1},如果这三个位置被占用,那就陷入了永远寻找下一个的无限循环中。

一般是限制probing function能返回刚好N个值。

当p(x)=ax的a与size的N互质,即没有公约数,GCD(a, N) = 1一般能产生刚好N个值。(Greatest Common Denominator)

注意,为了性能和效率的平衡,有load factor的存在,所以到了阈值,size就要加倍,N的变化,将会使得GCD(a, N) = 1的a的选择有变化,而且之前对N取模,现在取值也变发生变化,这时候需要重新map

重新map不再按元素当初添加的顺序,而是把现有HT里的值按索引顺序重新map一遍。比如第一个是k6, 即第6个添加进来的,但是现在第一个就重新计算它的值,填到新的HT里面去。

Quadratic Probing (QP)

QP 同样有chaos with cycles的问题,通用解决办法,三种:

  1. p(x) = $x^2$, size选一个 prime number > 3, and $\alpha \leq \frac{1}{2}$
  2. p(x) = $(x^2 + x) / 2$, keep the size a power of 2 (不需要是素数了)
  3. p(x)= $(-1^x) \times x^2$, make size prime N $\equiv 3$ mod 4 ???

Double Hashing

Double Hashing: P(x) = $x \times H_2(k)$可见仍然类似一个一次的线性方程,$H_2(k)$就类似于ax中的a,设为$\delta$,相比固定的a, 这里只是变成了动态的,这样不同的key的待选序列就是不一样的(可以理解为系数不同了)

解决chaos:

  1. size N to be a prime number
  2. calculate: $\delta = H_2(k)$ mod N
    • $\delta=0$ 时offset就没了,所以需要人为改为1
    • $1 \leq \delta \lt N$ and GCD($\delta$, N) = 1

可见,虽然系数是“动态”的了,但是取值还是(1,N)中的一个而已,hash只是让其动起来的一个原因,而不是参与计算的值。

我们本来就是在求hash value,结果又要引入另一个hash function,显然这个$H_2$不能像外层这样复杂,一般是针对常见的key类型(string, int...-> fundamental data type)的universal hash functions

因为N要是一个素数,所以在double size的时候,还要继续往上找直到找到一个素数为止,比如N=7, double后,N=14,那么最终,N=17

Issues with removing

因为冲突的hash value需要probing,probing的依据是从序列里依次取出下一个位置,检查这个位置有没有被占用,那么问题就来了,如果一个本被占用的位置,因为元素需要删除,反而变成没有占用了,这有点类似删除树节点,不但要考虑删除,还要考虑这个位置怎么接续。

lazy deletion 但HT机制比树要复杂,为了避免反复应用probing函数重新摆放后续所有节点,干脆就在删除的位置放置一个预设的标识,我们称为墓碑(tombstone),而不是直接置空,然后所有的查找和添加加上这一条规则,就能快速删除又无需重新排序。

大量删除会造成空间浪费,但无需立即处理:

  1. 添加元素允许添加到墓碑位置
  2. 到达阈值容量需要倍增的时候有一次重排,这个时候就可以移除所有的墓碑

如果查找一个hash value,连续3个都是墓碑,第4个才是它,这是不是有点浪费时间? 确实,所以还可以优化,当你查找过一次之后,就可以把它移到第一个墓碑的位置,这样,下次查询的时候速度就会快很多了。

整个机制,叫lazy deletion

数据结构篇四:Binary Trees and Binary Search Trees (BST)

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Tree: 满足以下定义的undirected graph(无向图)

  • An acyclic(非循环的) connected graph
  • N nodes and N-1 edges
  • 有且只有一条路径连接任意两个顶点

任意一个节点都可以被理解为root

Binary Tree 拥有最多两个节点的Tree

Binary Search Tree 服从以下特性的binary tree

  • 左子树的元素小于右子树

拥有重复元素是允许的,但多数情况下我们只研究不重复的元素

这是一个有效的BST吗?

是的(对于单链下来的,几乎会直接就满足右边比左边大)

Usage

  • BSTs
    • implementation of some map and set ADTs
    • red black trees
    • AVL trees
    • splay trees
    • ...
  • binary heaps
  • syntax trees (by compiler and calculators)
  • Treap - a probabilistic DS (uses a randomized BST)

Complexity 增删查平均为O(log n),但最差情况下都为O(n),即线性时间

Adding elements to a BST

  • 第一个为root
  • 每一个新数,比顶点大,放右边,比顶点小,放左边,顺序下行
    • 不是从左到右摆满再做subtree
    • 比如3,6,9, 会得一棵全部数字摆在右边的数,而不是顶3左6右9的三角形
    • 这也是为什么极端情况下,时间复杂度是O(n),因为就是一条线到底
    • 这也是balanced binary search trees被引入的原因

Removing elements from a BST

  • find
    • 从root开始,小的走左右,大的走右边
  • replace (to maintain the BST invariant)

找继任者的时候,如果删除元素没有子节点,只有左或右子节点,都很好办,但如果它有两个子节点,那么应该用哪个来接续呢?

原则仍然是要服从左边的比右边的小,所以你其实有两种选择:

  • 把左边最大的数选出来 或
  • 把右边最小的数选出来

因为它们的“来源”,肯定是能保证bst invariant的 * 这个数是要替换这个节点的,所以要比这个节点左边的数都大,及比右边所有的数都小,显然就是左边的最大数,或右边的最小数了。 * 只是把找到的元素复制过去后,多了的那个怎么办呢?

  • 递归

新找到的元素当然要从原来的位置删除,这时又根据它是否叶节点,单子节点还是全节点,来反复进行前面的操作,最终总是可以退出的

Tree Traversals

(Preorder, Inorder, Postorder & Level order)

  • preorder,在遍历左侧元素的时候,每次已经先取到元素了(最顶层)
  • inorder里,遍历元素的时候,直到所有的left走完了,才取到第一个元素(最底层的)
  • postorder里,也是遍历到最底层,但是下一步就是取兄弟节点了

inorder一个重要特征:它是从小到大排好序的!

preorder 和 postorder没什么特征,举一个post的例子观察下

而levelorder则是一一层地取的:

这就是广度优先了(Breadth First Searth)BFS

实现BFS

  1. 每处理一个parent的时候,把parent加到结果数组里
  2. parent的子节点加到队列里
  3. 每次从队列里取出一个值加到结果数组里(步骤1)
  4. 该值的child加到队列里(步骤2)

其实就是步骤1,2的重复,比如:

[11], [6, 15] 处理第1个数11, 队列里多了两个元素6, 15
[11, 6], [15, 3, 8] 从队列里取出6, 加入结果,它的子元素(3, 8)加入队列
[11, 6, 15], [3, 8, 13, 17]
[11, 6, 15, 3], [8, 13, 17, 1, 5]
[11, 6, 15, 3, 8], [13, 17, 1, 5] 这一步,8没有子节点了,队列变短了
[11, 6, 15, 3, 8, 13], [17, 1, 5, 12, 14]
[11, 6, 15, 3, 8, 13, 17], [1, 5, 12, 14, 19] 17只有一个child
[11, 6, 15, 3, 8, 13, 17, 1, 5, 12, 14, 19] 剩下的都没child了,全部拼进去

数据结构篇三:Union Find

这是一位 google 工程师分享的8小时的数据结构的视频,我的笔记


Union Find

  • keep track of elements in different sets
  • primary operations: find and union

Usage

  • Kruskal's minimum spanning tree algorithm
  • Grid percolation
  • Network connectivity
  • Least common ancestor in trees
  • Image processing

Complexity

  • construction: O(n)
  • union/join/size/check connected/: $\alpha$(n) :接近常量时间
  • count: O(1)

给定一个无向图,如果它任意两个顶点都联通并且是一棵树,那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图,那么权值之和最小的生成树,我们就称之为最小生成树(MST, Minimum Spanning Tree)。 -> 用最少的边连接所有的顶点

  • sort edges by ascending edge weight
  • walk through edges
    • 检查顶点,如果两个顶点都已经unified,就忽略
      • 其实就是这两个点分别被别的边连过了
    • 否则就添加edge,并且unify顶点

看到这里,首先想知道什么是unified,看实现,也就是在一个集合里(component)

  • 观察C_J,因为C和J已经在一个组里了,这条边就不需要了
  • 观察D_E,一旦连上后,紫色和绿色其实就是一个组了
  • 观察D_H,一旦连上后,紫色和红色也成为了一个组
  • 连接B_C,所有顶点就全部连上了,并且只有一条紫线

Find: 找元素在哪个component里,然后找到它的root Union: 找两个元素分别在哪个component里,然后找到它们的root,如果不是同一个root,就让其中一个成为另一个的parent

  • component的个数与root的个数一致
  • root的个数只减不增(因为通常只合并而不拆分)

union find里

  • 为每个元素分配一个索引,每个元素指向自己(即初始是n个root,n个component)
  • 描述两两之间的关系,以任一元素为parent (谁来描述?)
  • 有一个元素已经属于别的component里的,就将它也加到那个component里去
    • 如果这个元素也是别的component里的顶点,就把整个组指向另一个组的root

Path Compression Union Find

由一层层找到root改为所有顶点直接指向顶点(星形结构),实现路径压缩

这段代码演示的是,查找p的root节点,在查找的过程中,顺便进行了路径压缩

合并的逻辑就是比较谁的元素多就把谁当作root,另一个component的root的parent设为元素多的组的root
合并完成后组数就少了1

看代码,这一步里面并没有路径压缩,也就是小组里面的元素并没有进一步再星状地指向新的parent,仍然指向的是老的组的root。