帮我实现下面的功能:1.基于单链表设计一个完整的二又树ADT,将第一个元素的索引赋值为0。给定一个索引i,请执行三个操作分别得到它的父、左子和右子(8分)。 2.基于上面的完整二叉树,设计一个最小优先级队列。具体来说,你应该实现并解释insert0和delMin((英文写作风格将被判断,14分)。 3.在最小优先级队列(1分)中分析上述方法的时间复杂度。 4.为基于链表的堆执行一个简单的性能基准测试,并将结果可视化(5分)。 5.(奖励)基于你的链表堆,用graphviz绘制相应的树结构(5标记)。
时间: 2023-02-08 19:06:50 浏览: 283
实现关于链表的各种操作及排序
5星 · 资源好评率100%
对于第1个问题,首先可以设计一个单链表二叉树类,其中包含节点的值、左儿子的索引和右儿子的索引。接着,你可以定义三个方法来获取一个给定索引的节点的父亲、左儿子和右儿子,如下所示:
```python
class BinaryTree:
def __init__(self):
self.nodes = [None] # 第一个元素的索引为0
def get_parent(self, i):
if i == 0:
return None
return (i-1) // 2
def get_left_child(self, i):
return 2*i + 1
def get_right_child(self, i):
return 2*i + 2
```
对于第2个问题,你可以基于上面设计的单链表二叉树来设计一个最小优先级队列。为此,你需要实现一个insert()方法,用于在队列中插入新元素,并一直维护最小堆性质;以及一个delMin()方法,用于删除堆顶元素并重新维护最小堆性质。如下代码为示例实现,仅供参考:
```python
class MinHeap:
def __init__(self):
self.tree = BinaryTree()
self.tree.nodes.append(float("inf")) #哨兵
def insert(self, val):
self.tree.nodes.append(val)
i = len(self.tree.nodes)-1
while i>0:
p = self.tree.get_parent(i)
if self.tree.nodes[p]>self.tree.nodes[i]:
self.tree.nodes[p],self.tree.nodes[i]=self.tree.nodes[i],self.tree.nodes[p]
i=p
def delMin(self):
i=
阅读全文