//
//  main.swift
//  LearnDataStructures
//
//  Created by Weipeng Qi on 2020/10/24.
//

/*
 数据结构大体分为三类：
 线性结构：数组、栈、队列、链表、哈希表……
 树结构：二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie（字典树）、线段树、K-D树、并查集、霍夫曼树……
 图结构：邻接矩阵、邻接表……
 
 数据库中大量使用各种树结构以及哈希表等。
 操作系统中会有系统栈、优先队列（堆）。
 霍夫曼树用于文件压缩算法。
 Trie 微软实习生，通讯录联系人很多时，查找联系人变慢，使用 Trie 查找就会非常好
 
 图论算法：
 DFS（深度优先遍历） 使用栈
 BFS（广度优先遍历） 使用队列

 ----------

 这里学习的数据结构：

 【线性结构类】
 
 动态数组：动态数组基于静态数组，在静态数组的基础上通过 resize 方法实现容量可变。需要说明的是，Java 的静态数组容量不可变，但是元素可修改。Swift 的数组如果使用 let 修饰，则容量元素均不可改变，如果使用 var 修饰，则长度元素均可改变。

    增 O(n)
    删 O(n)
    改 已知索引 O(1) 未知索引O(n)
    查 已知索引 O(1) 未知索引O(n)
 
 链表：链表是最简单的动态数据结构。
 
    单链表各个操作时间复杂度：
    func append(value: T)                          O(1) // 如果不添加 tail 的话复杂度为 O(n)
    func insert(_ value: T, at index: 0)           O(1)
    func insert(_ value: T, at index: Int)         O(n)
    
    func removeAll()                               O(1)
    func remove(at index: Int) -> T                O(n)
    func removeFirst() -> T                        O(1)
    func removeLast() -> T                         O(n)
    
    linkedList[n] = newValue                       O(n)
    
    var first: T? { get }                          O(1)
    var last: T? { get }                           O(1) // 如果不添加 tail 的话复杂度为 O(n)
    linkedList[n]                                  O(n)
    func contains(_ value: T) -> Bool              O(n)
    
    也就是说，总体来讲，对于链表来说，增删改查全是 O(n) 级别的。
    但是如果只是对链表头进行操作，那么不管是增删改查，都是 O(1) 级别的。
    链表的复杂度主要是花费在查找节点上，而具体删除或者插入的操作是很方便的，这点和数组不同，数组体现在查找特别快，但是删除或者插入比较麻烦。
 
 栈：先进后出。
                 操作                   数组栈      链表栈
    var isEmpty: Bool { get }           O(1)       O(1)
    var count: Int { get }              O(1)       O(1)
    mutating func push(_ element: T)    O(1) 均摊   O(1)
    mutating func pop() -> T?           O(1) 均摊   O(1)
    func top() -> T?                    O(1)       O(1)
 两种栈性能相差不大，数组栈略好。
 
 队列：先进先出。
                 操作                    数组队列  改进后数组队列  链表队列
    var isEmpty: Bool { get }             O(1)      O(1)      O(1)
    var count: Int { get }                O(1)      O(1)      O(1)
    mutating func enqueue(_ element: T)   O(1) 均摊  O(1)均摊   O(1)
    mutating func dequeue() -> T?         O(n)      O(1)均摊   O(1)
    var front: T? { get }                 O(1)      O(1)      O(1)
 数组队列出队性能较差，后两者均较好，改进后的数组队列略好于链表队列。
 
 
 【树结构类】
 
 相关概念：
 二叉树、满二叉树、完全二叉树、平衡二叉树。
 其中满二叉树就是每层都铺满了，完全二叉树只有最后一次右边可能会没有铺满，平衡二叉树指的是一棵树最大深度和最小深度之差最多为 1。
 
 满二叉树 ⊂ 完全二叉树 ⊂ 平衡二叉树 ⊂ 二叉树
 
 二分搜索树：
 二分搜索树每一个节点的值都大于其左子树中所有节点的值，都小于其右子树中所有节点的值，所存储的元素必须具有可比较性。
 它不是一棵平衡二叉树，有可能退化为链表。
 
 集合：
 对于集合来说，主要涉及增、查、删的操作，不涉及改的操作。
        操作                                    链表集合   二分搜索树(复杂度   平均     最差)
 func insert(_ newMember: Element)              O(n)              O(h)  O(logn)  O(n)
 func remove(_ member: Element)                 O(n)              O(h)  O(logn)  O(n)
 func contains(_ member: Element) -> Bool       O(n)              O(h)  O(logn)  O(n)
 
 
 对于链表来说，由于没有索引，删除指定元素和查询指定元素都需要遍历，复杂度为 O(n)，添加元素操作由于要判重，也需要进行一次遍历，所以复杂度也是 O(n)。
 对于二分搜索树集合，它的增查删其实只是寻找了树的层树，我们用 h 表示
 最好的情况，也就是树是满的情况下层数和元素数的关系是 2^h - 1 = n，h = log(n + 1)    (log底是 2)
 那么最好情况的复杂度就是 O(logn) 级别的，这其实很接近 O(1) 级别，在数据量大的时候要比 O(n) 好得多
 但是对于二分搜索树来说，如果添加元素的时候恰好是从小到大或者相反地插入元素，这棵树就退化成链表了。
 要解决这个问题，就要使用平衡二叉树。
 
 映射：
            操作                                          链表映射        BSTMap     最优/平均     最坏
 func contains(_ key: Key) -> Bool                         O(n)          O(h)    O(logn)      O(n)
 subscript(key: Key) -> Value? { get set }                 O(n)          O(h)    O(logn)      O(n)
 func removeValue(forKey key: Key) -> Value?               O(n)          O(h)    O(logn)      O(n)
 
 映射可以使用链表实现，也可以使用二分搜索树实现，当然也可以使用哈希表实现，和集合是很像的。
 和集合不同的是，映射中每个节点不仅仅要包含一个值，而是要有一组键值对，所有我们无法直接使用之前实现的链表和二分搜索树中的接口，而需要重新实现。
 整体性能上可以参考集合的对比，依然是二分搜索树实现的优于链表实现的，之后哈希表实现的由于其无序，性能还会略好于搜索树实现的。
 复杂度水平都是和集合是相同的。
 
 堆：
 优先队列就是出队永远需要优先级对高的。优先队列针对的是动态的情况，如果是静态的，那么只需要排序一次即可。
 
 如果使用之前的线性数据结构实现优先队列，入队操作是 O(1)，但是出队操作需要遍历找到优先级最高的元素，因此是 O(n)。
 如果专门维护一个顺序的线性结构，也就是入队直接排序好，那么入队复杂度为 O(n)，出队复杂度为 O(1)。
 使用堆实现的优先队列，入队出队复杂度均为 O(logn)
 
 对于满二叉树，就是所有非叶子节点均既有左孩子，又有右孩子。
 完全二叉树不一定是满二叉树，但是其不满的部分一定是在树的右下侧。也就是除了最底层之外，上面的是一个满二叉树，最底层从左开始放置元素。
 
 二叉堆是一棵完全二叉树。
 堆中某个节点的值总是不大于其父节点的值，这叫做最大堆。相应也可以定义最小堆。
 
 因为二叉堆是一个完全二叉树，其实也能使用数组来表示这个完全二叉树，即分别按照层数从上倒下，从左到右放进数组，根节点放进索引为 1的位置，以此类推。
 
 放进数组后，假如某节点索引为 i，那么左孩子节点索引就是 2i，右孩子节点索引就是 2i+1，其父节点索引就是 i/2
 如果根节点位置直接放进索引为 0的位置，那么放进数组后，假如某节点索引为 i，那么左孩子节点索引就是 2i + 1，右孩子节点索引就是 2i+2，其父节点索引就是 (i - 1)/2
 对于完全二叉树，寻找最后一个非叶子节点的索引就是找最后一个节点的父亲节点
 
 需要注意的是，完全二叉树是不会退化为链表的，所以这个时间复杂度是可以一直保持的。
 
 我们实现的是二叉堆，相应的也就有三叉堆、四叉堆等等
 对于 d叉堆来说，层数有可能更少，这在有些操作上会让速度更快
 但是比如下沉操作，就要考虑 d 个子节点而不是 2 个
 
 更高级的堆还有 索引堆，它可以操作堆中的某个元素
 二项堆
 斐波那契堆
 
 优先队列：
 func enqueue(_ element: T)             O(logn)
 func dequeue() -> T?                   O(logn)
 
 线段树：
 经典面试问题，一面墙，每次可以在其中一端区间进行染色，染色可以覆盖之前的染色，若干次染色后，问某个区间内有几种颜色？

 可以使用数组解决这个问题，只需要遍历指定区间，复杂度为 O(n)
 而如果使用线段树解决，复杂度为 O(logn)

        使用数组实现   使用线段树
 更新     O(n)       O(logn)
 查询     O(n)       O(logn)


 对于线段树，不考虑添加和删除操作，线段树解决的问题，区间本身是固定的
 假定研究的问题是数组区间求和，数组共 8 个元素，则构造的线段树
                     A[0...7]
                   /          \
           A[0...3]             A[4...7]
          /     \               /       \
   A[0...1]    A[2...3]    A[4...5]    A[6...7]
    /    \       /   \      /     \      /    \
  A[0]  A[1]   A[2] A[3]  A[4]  A[5]   A[6]   A[7]

 根节点存储全部区间的和，A[0...3]存储前半段的和，以此类推。

 如果数组是 10 个元素，线段树则表示为
                     A[0...9]
                   /          \
           A[0...4]             A[5...9]
          /     \               /       \
   A[0...1]    A[2...4]    A[5...6]    A[7...9]
    /    \       /   \      /     \      /    \
  A[0]  A[1]   A[2] A[3,4] A[5]  A[6]  A[7]   A[8,9]
                     /  \                     /    \
                  A[3] A[4]                 A[8]  A[9]

 线段树不是满二叉树，更不是完全二叉树。
 线段树是一棵平衡二叉树。所谓平衡二叉树，是指一棵树最大深度和最小深度之差最多为 1。
 所以堆也是平衡二叉树，完全二叉树就一定是平衡二叉树。但是二分搜索树就不一定是平衡二叉树。
 平衡二叉树一定不会退化成链表。
 平衡二叉树可以近似看作一个满二叉树，也可以使用数组表示。

 对于线段树来说，如果使用数组来表示，如果区间有n个元素，那么数组需要4n的空间来存储。对于线段树我们不考虑添加元素，即区间固定。
 所以创建线段树复杂度为O(n)，准确的讲是O(4n)

 我们这里实现的线段树只能实现单个元素更新，没有实现区间更新。比如说，我们希望区间 [2,5]中所有元素 +3，在线段树中，需要将这个叶子节点以及他们的父节点都进行更新，复杂度会变为O(n)级别，比较慢。一个方式是进行懒惰更新，lazy更新，我们只把线段树中具体到相应区间的节点进行更新，其下面的子节点先不进行更新，而使用一个lazy数组记录未更新的内容，之后如果进行查询时先查找lazy数组看是否有未更新的内容，如果有再更新一下。

 线段树不仅仅适用于一维，二维甚至三维的区间问题都可以使用线段树解决。
 */
import Foundation

//let arrayTester = ArrayTester()
//arrayTester.test1()

//let stackTester = StackTester()
//stackTester.test1()
//stackTester.test2()
//stackTester.test3()

//let queueTester = QueueTester()
//queueTester.test1()
//queueTester.test2()
//queueTester.test3()
//queueTester.test4()

//let linkedListTester = LinkedListTester()
//linkedListTester.test1()
//linkedListTester.test2()

//let binarySearchTreeTester = BinarySearchTreeTester()
//binarySearchTreeTester.test1()

//let setTester = SetTester()
//setTester.test1()
//setTester.test2()

//let mapTester = MapTester()
//mapTester.test1()
//mapTester.test2()
//mapTester.test3()
//mapTester.test4()

//let segmentTreeTester = SegmentTreeTester()
//segmentTreeTester.test1()
