常考数据结构之队列、二叉树、堆

先进先出

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def append(self, val):
        return self.items.append(val)

    def pop(self):
        return self.items.popleft()

    def empty(self):
        return len(self.items) == 0


def test_qeue():
    q = Queue()
    q.append(0)
    q.append(1)
    q.append(2)
    q.append(3)
    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.pop())

test_qeue()

后进先出

from collections import deque

class Stack():
    def __init__(self):
        self.items = deque()

    def push(self, val):
        return self.items.append(val)

    def pop(self):
        return self.items.pop()

def test_stack():
    s = Stack()
    s.push(0)
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

test_stack()

二叉树
先序遍历
中序遍历
image.png

import heapq

class Topk():
    """获取大量元素topk 元素，固定内存
    思路：
    1、先放入元素前K个建立一个最小堆
    2、迭代剩余元素：
        如果当前元素小于堆顶元素，跳过该元素(肯定不是前K大)
        否则替代堆顶元素为当前元素，并重新调整堆
    """

    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k
        self.iterable = iterable

    def push(self, val):
        if len(self.minheap) >= self.capacity:
            min_val = self.minheap[0]
            if val < min_val: #当然你可以直接if val > min_val操作，这里只是显示指出跳过这个元素
                pass
            else:
                heapq.heapreplace(self.minheap, val) # 返回并且pop堆顶最小值，推入新的val值并调整堆
        else:
            heapq.heappush(self.minheap, val) # 前面k个元素直接放入minheap

    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap

def test():
    import random
    i = list(range(1000))
    random.shuffle(i)
    l = Topk(i, 10)
    print(l.get_topk()) # [990, 991, 996, 992, 995, 997, 998, 993, 994, 999]

test()