Data Structure

2018-08-15 本文已影响5人冒绿光的盒子

stack

heap

堆的基本性质：
①堆中的某一个节点总是不小于或不大于其父节点的值。
②堆总是一棵完全二叉树
比较经典的堆有二叉堆，费波纳茨堆等等。如果一棵二叉树最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

比如这就是一棵完全二叉树，而且是最小堆，最大堆就是反着来即可。但是并不是层数越高，堆的值就越小（大）

比如13就是小于15的，这样并不会违反最大堆的定义。
i堆的实现可以使用类似二叉树做左节点右节点的实现，定义一个类，左子树右子树和数组。但是基于堆的特殊性质，我们可以使用数组实现

从图中可以得到每一个左节点都是父节点的2倍，右节点是2倍加1。

heap的实现

实现一个最大堆。用一个类作为容器。为了存取方便，第一个元素从索引1开始。

class maxheap(object):
    def __init__(self):
        self.__array = [0]
        self.__count = 0
        pass

    def size(self):
        return self.__count

    def isEmpty(self):
        return self.__count == 0

上面都是些基本操作，查看大小，判断是否为空。

insertHeap

插入一个元素直接把插入的元素放在最后，但是还要注意需要满足最大堆的任何一个节点都不大于父节点，所以要做一个shifup的上浮操作，如果当前节点是大于父节点，当前节点和它的父节点交换，以此类推，知道不大于为止。
上浮操作：

    def __shifUp(self, k):
        while k > 1 and (self.__array[int(k/2)] < self.__array[k]):
            swap(self.__array, int(k/2), k)
            k = int(k/2)
        pass

首先要判断这个节点是不是最大的了，k=1是最大的了，如果不是，那么这个节点必有一个父节点，因为数组是依次排序下来的，大于就交换。
实现插入操作：

    def insert(self, number):
        self.__array.append(number)
        self.__count += 1
        self.__shifUp(self.__count)
        pass

插入之后把最后新进的元素进行上浮shifup操作即可。

extractMax

出堆只能是出最大的元素，也就是索引为1的元素，出堆之后哪个元素作为最大的元素也是需要交换的，这个时候就需要shifdown了。

    def __shifDown(self, k):
        while 2*k <= self.__count:
            j = 2*k
            if j + 1 <= self.__count and (self.__array[j + 1] > self.__array[j]):
                j += 1
            if self.__array[k] >= self.__array[j]:
                break
            swap(self.__array, k, j)
            k = j
        pass

先看一下这个元素有没有子节点，如果右节点也有，那就要比较一下两边哪个大，最后还要看一下当前节点是不是小于子节点，小于才交换。

    def extractMax(self):
        maxNumber = self.__array[1]
        self.__array[1] = self.__array[self.__count]
        self.__count -= 1
        self.__shifDown(1)
        return maxNumber
        pass

这就是主要的出堆了，拿出第一个元素之后直接把这个元素和最后一个元素交换，直接赋值也可以，接着下浮操作即可。

if __name__ == '__main__':
    heap = maxheap()
    for i in range(13):
        heap.insert(np.random.randint(0, 200))
    heap.showHeap()
    for i in range(1):
        print(heap.extractMax())
    heap.showHeap()

测试一下：

索引堆

之前学过的堆：

经过heapify之后：

这样存在的许多的数据交换，会有一些局限性，如果数据的内容特别大，每一个节点都是一个几十万的字符串，那么这样的消耗是非常大的。另外，他还有一个弊端，如果是一些进程，每一个进程下面的数字就是优先级，比如第一张图片1号进程优先级是15,2号17。heapify之后如果想要改变某一个进程的优先级就有点难了，当然也可以开辟一个空间存储ID，但是麻烦了点。
所以比较好的方法就是每一个节点分配一个索引，用索引来建堆。

建堆的时候不使用原值，而是用一个索引。交换也就是交换索引了。

首先交换的复杂度不高，想改变某个值重新建堆也很方便。

tree

二叉搜索树

二叉搜索树首先要讲到二分查找法。

二分查找

首先二分数据，查看中间的一个数据是不是要找的，如果不是就看是否大于，大于就查找右边，右边再次二分，小于查找左边，再次二分。这样不断迭代完即可。当然前提是这个数组要是有序的。

def binarySearch(array, n, target):
    '''
    :param array:order array
    :param n: the number of the array
    :param target: number which we search for
    :return: index of target
    '''
    l, r = 0, n-1
    while l <= r:
        mid = int((l + r)/2)
        #mid = int((l + (r-l))/2)
        if array[mid] == target:
            return (mid + 1)
        elif mid < target:
            l = mid + 1
        elif mid > target:
            r = mid - 1
    return -1

其实这里有一个bug，如果在求mid的时候，lr过大了，那么就容易出现溢出，这样就尴尬了。所以最后改进一下，既然是加法不行，那就来减法的，于是改进之后:

mid = int((l + (r-l))/2)

这样就可以了。

二分搜索树的优势

查找表：

如果键的值是整数，那么使用数组就可以达到目的。但如果像是字符串这些，就不能了，所以就出现了字典。实现查找表最基础的方式就是二分搜索树。

method	search	insert	delete
array	$O(n)$	$O(n)$	$O(n)$
order array	$O(logn)$	$O(n)$	$O(n)$
binary tree	$O(logn)$	$O(logn)$	$O(logn)$

二分搜索树在插入查找删除方面都是很有效率的。

每一个节点的键值大于左孩子，小于右孩子，以左右孩子为子树的节点仍为二分搜索树。上面讲的二叉堆一定是要完全二叉树，但是是二分搜索树就不一定是完全二叉树了，只要满足键值大于左孩子小于右孩子即可。

二分搜索树的实现

定义一棵二叉树：

class BST(object):
    class _node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
    def __init__(self):
        self.root = None
        self.count = 0

    def size(self):
        return self.count

    def isempty(self):
        return self.count == 0

定义一个节点，键值，对应的值，查找就是通过键值查找，而不是通过value查找。
插入：
插入就很简单了，递归选择左右子树插入，如果发现有重复的键值了，直接替换，没有就新建立一个。

    def insert(self, key, value):
        self.root = self.__insert(self.root, key, value)

    def __insert(self, node, key, value):
        if node == None:
            return self._node(key, value)
        elif key == node.key:
            node.value = value
        elif key < node.key:
            node.left = self.__insert(node.left, key, value)
        else:
            node.right = self.__insert(node.right, key, value)
        return node

是否包含：
和插入其实差不多，查找也是，都是那么几个判断：

    def contain(self, key):
        return self.__contain(self.root, key)

    def __contain(self, node, key):
        if node == None:
            return False
        elif node.key == key:
            return True
        elif key < node.key:
            return self.__contain(node.left, key)
        else:
            return self.__contain(node.right, key)

查找：

    def search(self, key):
        return self.__search(self.root, key)
        pass

    def __search(self, node, key):
        if node == None:
            return None
        elif node.key == key:
            return node.value
        elif node.key < key:
            return self.__search(node.right, key)
        else:
            return self.__search(node.left, key)
        pass

一言不合就递归。

二叉树的深度优先遍历

前序遍历：先访问当前节点，再依次递归访问左右子树。
中序遍历：先访问左子树，再访问自身节点，最后访问右子树。
后序遍历：先访问左右子树，最后再访问自身节点。

前序遍历：

中序遍历：

后序遍历：

二叉树每一个节点都会被访问三次，上面的三个点就代表了访问的三次，分别代表了前中后序，前序遍历就是只要到达了前序遍历的那个点才输出，中序遍历就是到达了中序遍历的那个点才输出，后序遍历也一样。
用递归处理其实很简单：


    def preOrder(self):
        self.__preOrder(self.root)
        pass

    def __preOrder(self, node):
        if node != None:
            print('key: ', node.key, ' value: ', node.value)
            self.__preOrder(node.left)
            self.__preOrder(node.right)

    def inOrder(self):
        self.__inOrder(self.root)
        pass

    def __inOrder(self, node):
        if node != None:
            self.__inOrder(node.left)
            print('key: ', node.key, ' value: ', node.value)
            self.__inOrder(node.right)
        pass

    def postOrder(self):
        self.__postOrder(self.root)
        pass

    def __postOrder(self, node):
        if node != None:
            self.__postOrder(node.left)
            self.__postOrder(node.right)
            print('key: ', node.key, ' value: ', node.value)

对于这些遍历的应用，一个就是释放元素的时候，在C++里面释放内存就可以使用后序遍历的方法了。

    def destory(self):
        self.__destory(self.root)
        pass

    def __destory(self, node):
        if node != None:
            self.__destory(node.left)
            self.__destory(node.right)
            del node

深度优先遍历是先以树的深度为准，左子树遍历完再遍历右子树。广度遍历是先以范围为准，先最大范围的遍历，层序遍历就是一个广度优先遍历。

二叉树的广度优先遍历

比如这么一棵二叉树，访问了28之后等于就是这一层完了，那么就要访问它的左右子叶，16，30。所以整个顺序就是

结果显示。四种遍历结果的显示。

删除最大值和最小值

寻找最小值其实就是不断的找左叶子的过程，选择最大值就是不断找右叶子的过程。

如果是这种情况，那么删除最小就很简单了，直接扔掉就好了，但如果是：

22有右孩子，那么直接把右孩子的那颗树拉上来就好了，因为任何一棵子树都是符合二叉树的性质，最大值也一样。这里是58，那么直接把子树拉上来就好了，最小值不可能有左子树，最大值不可能有右子树。
所以删除最大值和最小值就很简单了：

    def removeMin(self):
        if self.root != None:
            self.root = self.__removeMin(self.root)
            pass

    def __removeMin(self, node):
        if node.left == None:
            right = node.right
            del node
            self.count -= 1
            return right
        node.left = self.__removeMin(node.left)
        return node

    def removeMax(self):
        if self.root != None:
            self.root = self.__removeMax(self.root)
            pass

    def __removeMax(self, node):
        if node.right == None:
            left = node.left
            del node
            self.count -= 1
            return left
        node.right = self.__removeMax(node.right)
        return node

删除随便一个值

这个就和上面的有点不一样了，有三种情况，都有左右子叶，只有左子叶，只有右子叶，首先是如果有左右子叶：

要删除59，首先要从子树找一个可以替代的，右子树比左子树要大，所以肯定要从右子树选择，但是又要把右子树所以的元素都要小，所以要选择右子树最小的一个元素。就是59了。所以如果都有左右节点，那么就要找右子树最小的元素进行替代。如果是只有左子树或者是右子树，那就直接把左右子树拉上来就好了。

    def remove(self, key):
        self.__remove(self.root, key)
        pass

    def __remove(self, node, key):
        if node == None:
            return None
        elif node.key > key:
            node.left = self.__remove(node.left, key)
            return node
        elif node.key < key:
            node.right = self.__remove(node.right, key)
        else:
            if node.left == None:
                right = node.right
                del node
                self.count -= 1
                return right

            elif node.right == None:
                left = node.left
                del node
                self.count -= 1
                return left

            else:
                successor = copy.deepcopy(self.__minmum(node.right))
                successor.right = self.__removeMin(node.right)
                successor.left = node.left
                return successor

代码同样是很简单了，直接递归处理。

二叉树的总结

大多数情况下我们还是把二叉树当成是一种查找表来进行的，主要关注的任务主要就是如何查找一个key的value。
二叉树还有一个比较好的性质，它有一定的顺序性。首先就是最大值和最小值，已经实现过了，还有找前驱和后继的问题。还有一个，选择floor和ceil的问题，寻找最小上界最大下界，如果这个数是在二叉树里面存在的，那么就本身，如果不存在，如下：

二分搜索树的局限性，同一堆的数据，不同的插入顺序是会存在不同的二叉树的

这个时候，这个二叉树就会退化成一个链表，所以这时候就需要AVL树来调整了，比较经典的就是红黑树，而这棵树它的左右子树高度是不会超过1的。

并查集

首先是一个连接问题：

想知道相邻的两个点有没有连接，直接看有没有线就好了，但是如果我想找到左上角的点和右下角的点有没有连接，这就尴尬了。
所以并查集一个比较好的应用就是连接问题，网络之间的连接状态。比如用户之间形成的网络，看看这个用户能不能通过好友认识另外一个人。就是qq可能认识的人。

路径问题和连接问题

连接问题比路径问题要回答的问题少，连接问题只需要回答是不是连接的即可，而路径问题就要回答哪条路径是最短的。所以连接问题会比路径问题要快。对于排序也是一样，查找一个元素，二分查找是很快的，比顺序查找要快，因为顺序查找其实回答了更多的问题，比如这个元素排名第几，查找任意一个元素等等。选择问题也是一样，快排更块，因为它只是找了这个元素，其他回答的问题更多，所以时间更长。

并查集的构成和作用

并查集要支持的主要就是两个操作：
union(p,q)连接两个节点pq
find(p)查找p是哪个组的
isConnected(p,q)两个节点是否连接在一起的。
并查集可以用最简单的的一个方法表示，只用一个数组和下标表示：

0到4都是0，所以0到4着5个元素是互相连接的。5到9都是1那么就是互相联系的。

这样就是奇数互相联系，偶数互相联系。简单实现一些，union的version1：

class UnionFind(object):
    id = None
    count = 0

需要有一个数组，也就是id，需要一个数量count。

    def unionFind(self, n):
        self.count = n
        self.id = np.zeros(n)
        for i in range(n):
            self.id[i] = i

创建一个并查集

    def find(self, p):
        if p >= 0 and p < self.count:
            return self.id[p]

找到当前数字的id号是多少。

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)
        pass

判断他们之间是否有联系。

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        for i in range(self.count):
            if self.id[i] == pID:
                self.id[i] = qID
            pass

两个元素拉上联系。这种方式实现的并查集查找方式很快，但是union的方法就会很慢。union是 $logn$ 。

并查集的另一种实现思路

上面一种的实现方式我们称为是quick find方法，查找方式是很快的，但是union操作就很慢，所以现在要实现一种比较高效的方法。
首先将每一个元素看成是一个节点，用一个数组的下标来存储和这个节点[图片上传中...(M}7EXC0KSP_(N2})M%MD6P.png-89c85b-1534299092134-0)]
合并的另一个节点，所以一开始，每一个节点都是指向自己，因为没有其他节点和他一起：

现在如果想union(4, 3)，那就要把4放在3下，因为3的下标就是指向了和他union的那个点：

有点像树的结构，后的union都是互相合并根节点即可。现在要union(3, 8)，一般都是前一个指后面的一个，这样4也会跟着指过去：

同样union(6, 5)：

如果合并的是(9, 4)，那就是不是接4下面了，因为4下面有3了，所以如果是合并，接的是根节点，所以找4的根节点，4下面的是3,3下面的是8,8下面是8，所以8就是根节点，所以就要把9下面的9变成8了：

union(2, 1)

就是这样的合并方式。我们想找到两个节点是不是有联系的，只需要找到他们的根看看是不是一样的，所以现在简单实现一些代码：

class unionFind_version2(object):
    parent = None
    count = 0

    def unionFind_version2(self, count):
        self.parent = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        self.parent[pID] = qID

代码实现也很简单了。

并查集version2版本的优化

有一个特殊的情况，事实上union(9, 4)和union(4, 9)是一样的，但是有时候会出现极端的情况：

如果是(4, 9)

如果是(9, 4)

明显是第二种好，链太长对于两个元素的查找都会消耗很大的时间。所以可以改进一下，增加一个size数组，然后合并前看看哪个元素对应的树是最小的，最小的哪个就合并过来。

class unionFind_version3(object):
    parent = None
    size = None
    count = 0

    def unionFind_version3(self, count):
        self.parent = np.zeros(count)
        self.size = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i
            self.size[i] = 1

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        if self.size[pID] < self.size[qID]:
            self.parent[pID] = qID
            self.size[qID] += self.size[pID]
        else:
            self.parent[qID] = pID
            self.size[pID] += self.size[qID]

再次优化

事实上还是存在着极端的情况：

如果是合并，那么就会出现：

事实上：

这样才是比较好的合并方式，所以合并到哪一个并不应该通过数量来判断，而是通过树的高度来判断，也就是rank。

代码实现：

class unionFind_version4(object):
    parent = None
    rank = None
    count = 0

    def unionFind_version4(self, count):
        self.parent = np.zeros(count)
        self.rank = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i
            self.rank[i] = 1

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        if self.rank[pID] < self.rank[qID]:
            self.parent[pID] = qID
        elif self.rank[qID] < self.rank[pID]:
            self.parent[qID] = pID
        else:
            self.parent[pID] = qID
            self.rank[qID] += 1

要注意的其实就是最后一个union操作了，如果是小于的话改变不需要改变，因为合并之后还是高度不变，如果都是一样的，那么无论是合并到那一课树上都会存在rank+=1的情况。

路径压缩 Path Compression

之前的union合并可能会出现这样一种情况：

这样明显是不好的，没一次查找就相当于是遍历，所以可以考虑把4节点往上拉一下：

再往上拉一下：

把当前节点连上他parent节点的parent节点上，所以只需要修改一下find：

        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                self.parent[p] = int(self.parent[int(self.parent[p])])
                p = int(self.parent[p])
            return p

刚刚那种形式还可以再压缩，因为如果可以直接接到根节点的话查找是更加快的。

压缩成这种形式，查找的速度更加快，再次优化：

        if p >= 0 and p < self.count:
            if p != int(self.parent[p]):
                self.parent[p] = int(self.find(int(self.parent[p])))
            return int(self.parent[p])

通过递归处理，如果当前节点不是，那就让它的节点等于它的根。而在递归回去的时候把经过的节点都处理了。

图 Graph

图一般就是用于解决以上结构的一种数据结构。图主要由两部分构成，节点Vertex和边Edge。
图也分两类，无向图和有向图。

无向图

有向图
下面所讲的算法都将是围绕无向图展开，但是事实上这些算法也是同样适用于有向图，因为无向图也是一种特殊的有向图：

根据权重，图也可以分为有权图和无权图。如果每一条边都是没有权值的，单单就是一条边，那么就是无权图了。
图的连通性：

这三个图就是不连通的。
简单图：就是有自环边和平行边。

事实上这两个边没有意义的，自环边是没有用的，平行边在最小路径的时候，只要选择最小的那条边就好了。

图的表示方法

1.比较简单的方法就是邻接矩阵了，用一个矩阵来表示一个图。

可以使用一个矩阵来表示，01相连，那么0到1和1到0就是1了，因为是无向图，所以是左右对称的，当然这个图也是可以变成有向图表示的，无向图的话是对称，symmetrical。有向图不是对称的就是了。

2.邻接表的表示方法

首先是用一个数组来表示所以的节点，如果是有链接那么就再和有链接的节点下面用一个链表连上即可。首先邻接表肯定是比邻接矩阵的空间要小，而且邻接矩阵可能会是一个稀疏矩阵，浪费很多空间。所以，邻接矩阵适合表示一个稀疏矩阵，邻接表适合表示稠密矩阵。

图的实现

邻接矩阵的实现

class DenseGraph(object):
    n, m = None, None
    directed = None
    __g = None
    def __init__(self, n, directed):
        self.n = n
        self.m = 0
        self.directed = directed
        self.__g = np.array((n, n))
    def v(self):
        return self.n

    def e(self):
        return self.m

    def addEdge(self, v, w):
        if self.hasEdge(v, w) == 1:
            return
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                self.__g[v][w] = 1
                if self.directed != True:
                    self.__g[w][v] = 1
                self.m += 1
        pass

    def hasEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                return self.__g[v][w]

邻接表的实现

class SparseGraph(object):
    n, m = None, None
    directed = None

    def __init__(self, n, directed):
        self.n = n
        self.directed = directed
        self.__g = list()
        for i in range(n):
            self.__g.append(list())

    def v(self):
        return self.n

    def e(self):
        return self.m

    def addEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                self.__g[v].append(w)
                if v != w and self.directed != True:
                    self.__g[w].append(v)
                self.m += 1

    def hasEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                for i in range(len(self.__g[v])):
                    if self.__g[v][i] == w:
                        return True
                return False

图的遍历

遍历邻边

这是一种比较简单的遍历方式，遍历每一个节点和他相连的节点：

如果是邻接矩阵的形式，那么就需要遍历每一行，看看哪一个是1，是1的就拿出来。所以邻接矩阵的复杂度是

O(v^2)

；换成邻接表就很简单了，因为每一个节点下面链接的就是和他链接的节点，直接遍历就好了，所以是

O(v)

。
常规实现就是遍历，不按套路出牌，实现一个迭代器来进行迭代处理。邻接矩阵的迭代器实现：

    class FormIterator(object):
        G = None
        __g = None
        v = None
        index = None

        def __init__(self, G, v):
            self.G = G
            self.__g = G._DenseGraph__g
            self.v = v
            self.index = -1
            pass

        def begin(self):
            self.index = -1
            return self.next()

        def next(self):
            for self.index in range(self.index + 1, self.G.v()):
                if self.__g[self.v][self.index] == 1:
                    return self.index
            return -1

        def end(self):
            if self.index == self.G.v()-1:
                self.index += 1
                return True
            return self.index < self.G.v()

起始，下一个，结束，结束条件有多加了判断，因为源代码是C plus plus写的，for循环有些不一致，翻译成python代码就有点问题，所以多加了一个判断。
邻接表：

    class MatrixIterator(object):
        __g = None
        v = 0
        index = 0
        def __init__(self, G, v):
            self.__g = G._SparseGraph__g
            self.v = v
            self.index = 0
            pass

        def begin(self):
            self.index = 0
            if len(self.__g[self.v]) > 0:
                return self.__g[self.v][self.index]
            return -1

        def next(self):
            self.index += 1
            if self.index < len(self.__g[self.v]):
                return self.__g[self.v][self.index]
            return -1

        def end(self):
            return self.index >= len(self.__g[self.v])

这个也是一样。