常考数据结构之队列、二叉树、堆
2019-04-21 本文已影响0人
慕止
先进先出
先序遍历
中序遍历
image.png
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()