第八章总结

# 最小堆封装
from heapq import *
import pprint
class MinHeap:
    def __init__(self, iterable):
        self._iteralbe = []
        self._max = 1000
        self.linearpush(iterable)
    # 添加
    def push(self, item):
        heappush(self._iteralbe, item)
    # 弹出
    def pop(self):
        res = None
        try:
            res = heappop(self._iteralbe)
        except Exception as e:
            pprint.pprint(e)
        return res
    # 一个组合动作，先添加后弹出
    def pushpop(self, item):
        res = None
        try:
            res = heappushpop(self._iteralbe, item)
        except Exception as e:
            pprint.pprint(e)
        return res
    # 一个组合动作，先弹出再添加
    def replace(self, item):
        res = None
        try:
            res = heapreplace(self._iteralbe, item)
        except Exception as e:
            pprint.pprint(e)
        return res
    # 线性将列表加入到堆中，并且将原来的列表设置成堆
    def linearpush(self, iterable):
        for it in iterable:
            self._iteralbe.append(it)
        heapify(self._iteralbe)
    # 将所有列表合并到堆中
    def mergeAll(self, *iterables):
        arrs = [sorted(x) for x in iterables]
        arrs.append(self._iteralbe)
        self._iteralbe = list(merge(*tuple(arrs)))
    # 返回n个最大值
    def nlagrge(self, n):
        if n == 1:
            return max(self._iteralbe)
        l = len(self._iteralbe)
        if l != 0:
            if l < self._max:
                return nlargest(n, self._iteralbe)
            else:
                return sorted(self._iteralbe, reversed=True)[:n]
        return None
    # 返回n个最小值
    def nsmall(self, n):
        if n == 1:
            return self.getMin()
        l = len(self._iteralbe)
        if l != 0:
            if l < self._max:
                return nsmallest(n, self._iteralbe)
            else:
                return sorted(self._iteralbe)[:n]
        return None
    # 返回最小值
    def getMin(self):
        if len(self._iteralbe) == 0:
            return None
        else:
            return self._iteralbe[0]
a = [10, 2, 9, 4, 3, 5, 8, 6, 7, 1]
heap = MinHeap(a)
print("最小值是 {0}".format(heap.getMin()))
print("先添加后弹出是 {0}".format(heap.pushpop(0)))
print("先弹出后添加是 {0}".format(heap.replace(0)))
print("最小值是 {0}".format(heap.pop()))
print("前20个最大值是 {0}".format(heap.nlagrge(20)))
print("前2个最小值是 {0}".format(heap.nsmall(2)))
heap.mergeAll([8, 2, 4], [9, 10, -1])
print("合并之后的最小值是 {0}".format(heap.getMin()))

# 优先队列封装
import itertools
class priority_deque:
    def __init__(self):
        self.deque = []
        self.entry_findeer = {}
        self.conter = itertools.count()  # 用来处理优先级相同的任务
    def add_task(self, task, priority= 0):
        if task in self.entry_findeer:
            self.remove_task(task)
        count = next(self.conter)
        entry = [priority, count, task]
        self.entry_findeer[task] = entry
        heappush(self.deque, entry)
    def remove_task(self, task):
        if task in self.entry_findeer:
            self.entry_findeer.pop(task)
    def pop_task(self):
        while self.deque:
            return heappop(self.deque)
deque = priority_deque()
deque.add_task("第一个任务")
deque.add_task("第二个任务")
print(deque.pop_task())
print(deque.pop_task())

import bisect
def index(a, x):
    ‘Locate the leftmost value exactly equal to x‘
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError
def find_lt(a, x):
    ‘Find rightmost value less than x‘
    i = bisect.bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError
def find_le(a, x):
    ‘Find rightmost value less than or equal to x‘
    i = bisect.bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError
def find_gt(a, x):
    ‘Find leftmost value greater than x‘
    i = bisect.bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError
def find_ge(a, x):
    ‘Find leftmost item greater than or equal to x‘
    i = bisect.bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

import types
# Methods
def __init__(self, name, shares, price):
    self.name = name
    self.shares = shares
    self.price = price
def cost(self):
    return self.shares * self.price
cls_dict = {
    ‘__init__‘ : __init__,
    ‘cost‘ : cost,
}
Stock = types.new_class(‘Stock‘, (), {}, lambda ns: ns.update(cls_dict))
Stock.__module__ = __name__
s = Stock(‘ACME‘, 50, 91.1)
print(s.cost())