However, inserting into a list is 𝑂(𝑛)O(n)O(n) and sorting a list is 𝑂(𝑛log𝑛)O(nlogn)O(n \log{n}). We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in 𝑂(log𝑛)O(logn)O(\log{n}).
二叉堆
self.head = temp
update the head if the temp is the first node need to add
Try it yourself using ActiveCode 4.
class LogicGate: def init(self, lbl): self.label = lbl self.output = None
def get_label(self):
return self.label
def get_Output(self):
self.output = self.perform_gate_logic()
return self.output
class BinaryGate(LogicGate): def init(self, lbl): LogicGate.init(self, lbl) self.pin_a = None self.pin_b = None
def get_pin_a(self):
return int(input(f"Enter pin A input for gate \
{self.get_label()}: "))
def get_pin_b(self):
return int(input(f"Enter pin B input for gate \
{self.get_label()}: "))
def set_next_pin(self, source):
if self.pin_a is None:
self.pin_a = source
else:
if self.pin_b is None:
self.pin_b = source
else:
raise RuntimeError("Error: NO EMPTY PINS")
class UnaryGate(LogicGate): def init(self, lbl):
# super(UnaryGate, self).__init__(lbl)
# super().__init__("UnaryGate", lbl)
super().__init__(lbl)
self.pin = None
def get_pin(self):
return int(input(f"Enter pin input for gate \
{self.get_label()}: "))
def set_next_pin(self, source):
if self.pin is None:
self.pin = source
else:
print("Cannot Connect: NO EMPTY PINS on this gate")
class AndGate(BinaryGate): def init(self, lbl): print('hello, and gate') super().init(lbl)
def perform_gate_logic(self):
a = self.get_pin_a()
b = self.get_pin_b()
if a == 1 and b == 1:
return 1
else:
return 0
class OrGate(BinaryGate): def init(self, lbl): super().init(lbl)
def perform_gate_logic(self):
a = self.get_pin_a()
b = self.get_pin_b()
if a == 1 or b == 1:
return 1
else:
return 0
class NorGate(OrGate): def perform_gate_logic(self): if super().perform_gate_logic() == 1: return 0 else: return 1
class NotGate(UnaryGate): def init(self, lbl): super().init(lbl)
def perform_gate_logic(self):
return 0 if self.get_pin() else 1
class NandGate(AndGate): def init(self, lbl): print('hello, Nand gate') super().init(lbl)
def perform_gate_logic(self):
# a = self.get_pin_a()
# b = self.get_pin_b()
# return 0 if a == 1 and b == 1 else 1
if super().perform_gate_logic() == 1:
return 0
else:
return 1
class Connector: def init(self, fgate, tgate): self.from_gate = fgate self.to_gate = tgate
tgate.set_next_pin(self)
def get_from(self):
return self.from_gate
def get_to(self):
return self.to_gate
def get_pin_a(self):
if self.pin_a == None:
return input(
f"Enter pin A input for gate \
{self.get_label()}: "
)
else:
return self.pin_a.get_from().get_output()
if name == 'main': g1 = AndGate("G1")
# g2 = NandGate("G2")
# print(g2.get_Output())
g2 = AndGate("G2")
g3 = OrGate("G3")
g4 = NotGate("G4")
c1 = Connector(g1, g3)
c2 = Connector(g2, g3)
c3 = Connector(g3, g4)
print(g4.get_Output())
immutable
不可改变的
homogeneous
同类事物
an actual parameter value upon invocation.
调用时的实际参数值
right-aligned
center-aligned, not right-alighed
milliseconds
1,000 milliseconds in a second, 毫秒
prerequisites
pre|req|ui|site 先决条件
probe
探索，探查
systematic
有条理的
Write a function buildTree that returns a tree using the list of lists functions that looks like this:
have not finished
If we wanted to translate the Java back to Python we would have something like the following class definition.
the sample jave 2 python program.
m.push('x') m.push('y') m.push('z') while not m.isEmpty(): m.pop() m.pop()
the second time have two m.pop() while the stack is already empty.