栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

1.数据结构堆

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

1.数据结构堆

1.Swift中没有像Java中的堆数据结构

2. 思路

这就是用典型的用小顶堆思路来解决

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        let minQ = PriorityQueue<(Int, Int)>.init { arr1, arr2 in
            return arr1.1  < arr2.1
        }
        
        let dict = nums.reduce(into: [:]) { partialResult, curVal in
            partialResult[curVal, default: 0] += 1
        }
        
        for key in dict.keys {
            let count = dict[key]!
            if minQ.count < k {
                minQ.push((key, count))
            } else {
                if minQ.peek()!.1 <= count {
                    minQ.poll()
                    minQ.push((key, count))
                }
            }
        }
        
        var arr = [Int]()
        for (i,_) in minQ.elements {
            arr.append(i)
        }
        
        return arr
    }
    
}
typealias PriorityBlock = (T, T) -> Bool

class PriorityQueue {
    
    var elements = [T]()
    var count: Int {
        return elements.count
    }
    
    var compartor: PriorityBlock
    init(_ block: @escaping PriorityBlock) {
        compartor = block
        elements = [T]()
    }
    
    public func push(_ val: T) {
        elements.append(val)
        siftUp(count - 1)
    }
    
    // 看一眼堆顶元素是什么
    public func peek() -> T? {
        if count == 0 {
            return nil
        }
        
        return elements.first!
    }
    
    // 拿出堆顶元素
    public func poll() -> T? {
        if count == 0 {
            return nil
        }
        elements.swapAt(0, count - 1)
        let ele = elements.removeLast()
        siftDown(0)
        
        return ele
    }
    
    // 上滤
    private func siftUp(_ index: Int) {
        guard index > 0 else { return }
        let parent = (index - 1) / 2
        if compartor(elements[index], elements[parent]) {
            elements.swapAt(index, parent)
            siftUp(parent)
        }
    }
    
    // 下滤
    private func siftDown(_ index: Int) {
        var parent = index
        let left = index * 2 + 1
        let right = index * 2 + 2
        
        if left < count && compartor(elements[left], elements[parent]) {
            parent = left
        }
        
        if right < count && compartor(elements[right], elements[parent]) {
            parent = right
        }
        
        if parent != index {
            elements.swapAt(index, parent)
            siftDown(parent)
        }
    }
    
}

Swfit封装的堆详解:

typealias PriorityBlock = (T, T) -> Bool

class PriorityQueue {
    
    var elements = [T]()
    var count: Int {
        return elements.count
    }
    
    var compartor: PriorityBlock
    init(_ block: @escaping PriorityBlock) {
        compartor = block
        elements = [T]()
    }
    
    public func push(_ val: T) {
        elements.append(val)
        siftUp(count - 1)
    }
    
    // 看一眼堆顶元素是什么
    public func peek() -> T? {
        if count == 0 {
            return nil
        }
        
        return elements.first!
    }
    
    // 拿出堆顶元素
    public func poll() -> T? {
        if count == 0 {
            return nil
        }
        elements.swapAt(0, count - 1)
        let ele = elements.removeLast() // 先把最后一个移除掉
        siftDown(0)                     // 再进行下滤
        
        return ele
    }
    
    // 上滤
    private func siftUp(_ index: Int) {
        guard index > 0 else { return }
        let parent = (index - 1) / 2                        // 小顶堆,小的值要在上面
        if compartor(elements[index], elements[parent]) { // 当前位置和父节点位置比较,如果比父节点位置的值小,就交换
            elements.swapAt(index, parent)
            siftUp(parent)
        }
    }
    
    // 下滤
    private func siftDown(_ index: Int) {
        var parent = index
        let left = index * 2 + 1
        let right = index * 2 + 2
        
        if left < count && compartor(elements[left], elements[parent]) { // 如果左边的比父节点值小,就交换,父节点就准备下沉到左边去
            parent = left
        }
        
        if right < count && compartor(elements[right], elements[parent]) { // 如果右边比左边的值更小,就交换,让父节点沉到右边去
            parent = right
        }
        
        if parent != index {
            elements.swapAt(index, parent)
            siftDown(parent)
        }
    }
    
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/943456.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号