基本功能实现——堆有两点需要了解，一是堆一般采用完全二叉树；二是堆中的每一个节点都大于其左右子节点（大顶堆），或者堆中每一个节点都小于其左右子节点（小顶堆）。
class heap(object): def __init__(self): self.data_list = [] #初始化一个空堆，使用数组来存放堆元素，节省存储 def get_parent_index(self, index): #返回父节点的下标 if index == 0 or index > len(self.data_list) - 1: return None else: return (index - 1) >> 1 def swap(self, index_a, index_b): #交换数组中的两个元素 self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a] def insert(self, data): #先把元素放在最后，然后从后往前依次堆化 #这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后 self.data_list.append(data) index = len(self.data_list) - 1 parent = self.get_parent_index(index) #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆) while parent is not None and self.data_list[parent] < self.data_list[index]: self.swap(parent, index) index = parent parent = self.get_parent_index(parent) def removeMax(self): #删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化 remove_data = self.data_list[0] self.data_list[0] = self.data_list[-1] del self.data_list[-1] #堆化 self.heapify(0) return remove_data def heapify(self, index): total_index = len(self.data_list) - 1 while True: maxvalue_index = index if 2*index + 1 <= total_index and self.data_list[2*index+1] > self.data_list[maxvalue_index]: maxvalue_index = 2*index + 1 if 2*index + 2 <= total_index and self.data_list[2*index+2] > self.data_list[maxvalue_index]: maxvalue_index = 2*index + 2 if maxvalue_index == index: break self.swap(index, maxvalue_index) index = maxvalue_index举例，将元素 1-10 放进堆，并展示建堆情况，及删除堆顶元素情况
class heap(object): def __init__(self): self.data_list = [] #初始化一个空堆，使用数组来存放堆元素，节省存储 def get_parent_index(self, index): #返回父节点的下标 if index == 0 or index > len(self.data_list) - 1: return None else: return (index - 1) >> 1 def swap(self, index_a, index_b): #交换数组中的两个元素 self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a] def insert(self, data): #先把元素放在最后，然后从后往前依次堆化 #这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后 self.data_list.append(data) index = len(self.data_list) - 1 parent = self.get_parent_index(index) #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆) while parent is not None and self.data_list[parent] < self.data_list[index]: self.swap(parent, index) index = parent parent = self.get_parent_index(parent) def removeMax(self): #删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化 remove_data = self.data_list[0] self.data_list[0] = self.data_list[-1] del self.data_list[-1] #堆化 self.heapify(0) return remove_data def heapify(self, index): total_index = len(self.data_list) - 1 while True: maxvalue_index = index if 2*index + 1 <= total_index and self.data_list[2*index+1] > self.data_list[maxvalue_index]: maxvalue_index = 2*index + 1 if 2*index + 2 <= total_index and self.data_list[2*index+2] > self.data_list[maxvalue_index]: maxvalue_index = 2*index + 2 if maxvalue_index == index: break self.swap(index, maxvalue_index) index = maxvalue_index if __name__ == "__main__": myheap = heap() for i in range(10): myheap.insert(i+1) print(\'建堆:\', myheap.data_list) print(\'删除堆顶元素:\', [myheap.removeMax() for _ in range(10)]) #输出 建堆: [10, 9, 6, 7, 8, 2, 5, 1, 4, 3] 删除堆顶元素: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 图图的分类
* 无向图 图是若干个顶点(Vertices)和边(Edges)相互连接组成的。边仅由两个顶点连接，并且没有方向的图称为无向图。
* 有向图 在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务调度的依赖关系，社交网络的任务关系等等都是天然的有向图。
图的实现——表示图通常有四种方法：数组表示法、邻接表、十字链表和邻接多重表。邻接表是图的一种链式存储结构，十字链表是有向图的另一种链式存储结构，邻接多重表是无向图的另一种链式存储结构。这里主要讲解一下邻接表的表示和实现，邻接表中有两种结点，一种是头结点，另一种是表结点，头结点中存储一个顶点的数据和指向链表中第一个结点，表结点中存储当前顶点在图中的位置和指向下一条边或弧的结点，表头结点用链式或顺序结构方式存储。
无向图的实现